Highest Value Palindrome

Woke up around 04:10 AM and decided to go back to sleep. Later I got up at 05:00 AM. Seems like another cold morning in the Twin Cities of Minneapolis and St. Paul. The skies were clear and it seems we have a full moon.

Yesterday I worked on the Highest Value Palindrome challenge at HackerRank. I was able to complete it but did not have time to generate a post. Hopefully it will be done in an hour or so.

For our immediate purpose, a palindrome is a sequence of decimal numbers that when read forward or backwards contains the same digits. For example 12321 is a palindrome, while 9129 is not. For additional information on a palindrome you can read here.

The challenge is to alter a numeric string of decimal characters, one at a time, and generate the highest possible palindrome. The challenge provides the length of the numeric string, the number of changes allowed and the actual string of numbers. Not sure why the length of the numeric string is provided given that one could get it with a single statement (String.length()).

It took me some time and several examples to completely understand what was requested and come with an approach. Given that we are dealing with a palindrome it made sense to traverse the string in both directions. That was easy. I was able to generate a palindrome, but it was not the highest possible one. We had to go back and undo some of the changes replacing some digits with ‘9’. I also figured that the string could have an even or uneven count of numbers. By replacing the middle digit with a ‘9’ we could get closer to the largest palindrome. For example, in the string 101, if we replace the middle digit with a ‘9’, we would get 191 which is larger than 101.

One more detail that is of importance is the fact that we need to use two passes. It is important to recall where the changes occurred in the first pass to optimize changes when we try to increase the representation of the numeric string.

OK, with that said, give it a try and let’s compare results:

	// Complete the highestValuePalindrome function below.
    static String highestValuePalindrome(String s, int n, int k) {
    	
    	char[] pal = s.toCharArray();
    	
    	// **** initialize indices ****
    	int l = 0;
    	int r = s.length() - 1;
    	
    	// **** attempt to make the string a palindrome ****  	
    	while (l < r) {
    		
    		// **** replace left and right by their max ****
    		if (s.charAt(l) != s.charAt(r)) {
    			pal[l] = pal[r] = (char)Math.max(s.charAt(l), s.charAt(r));
    			k--;	
    		}
    		
    		// **** updated indices ****
    		l++;
    		r--;
    	}
     	
    	// **** check if we are done **** 
    	if (k < 0) {
    		return "-1";
    	}
    	
    	// **** initialize indices ****
    	l = 0;
    	r = s.length() - 1;
    	
    	// **** second pass (check if we can update digits to '9') ****
    	while (l <= r) { // **** change mid character to '9' **** if ((l == r) && (k > 0)) {
    			pal[l] = '9';
    		}

    		// **** check on left character ****
    		if (pal[l] < '9') { // **** we can update them with cost of 2 **** if (k >= 2 &&
    				pal[l] == s.charAt(l) && 
    				pal[r] == s.charAt(r)) {
    				pal[l] = pal[r] = '9';
    				k -= 2;
    			}
    			
    			// **** we can update them with cost 1 ****
    			else if (k >= 1 &&
    					(pal[l] != s.charAt(l) || pal[r] != s.charAt(r))) {
     				pal[l] = pal[r] = '9';
       				k--;
    			}	
    		}
    		     		
    		// **** updated indices ****
    		l++;
    		r--;
    	}
    	
    	// **** ****
    	return new String(pal);
     }

To test while developing the solution I used the following data:

4 1
3943

3993


6 3
092282

992299


6 3
092182

292292


4 1
0011

-1


5 1
01011

11011


6 1
119911

119911


5 3
43435

93939

Each set of numbers contains the length of the string, the number of allowed changes and the initial numeric string. The last string in the set is the resulting palindrome. Note one string is already a palindrome and another cannot be converted given the number of changes allowed.

If you want to see the full solution you can find it in my GitHub repository.

If you have comments or questions regarding this or any other post in this blog, or if you have a challenge and need some help, feel free to drop me a message below.

Keep on learning and enjoying software development;

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.