I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler:K Palindromes

08.29.2013
| 5331 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

K Palindromes

You probably already know what a palindrome is: a string to results in the same word, whether read left to right, or right to left. A K Palindrome is when a string can be tranformed into a palindrome by changing K characters at most. Regular palindromes have K=0. 

Your challenge today is to write a method which takes a string and a value for k and returns true if it the string qualifies as a K palindrome. 


Catch up on all our previous puzzlers here

Comments

Vitalii Tymchyshyn replied on Thu, 2013/08/29 - 10:03pm

I hope "change" means character change to any other, not in-line character exchange.
    static boolean isPalindrome(String line, int maxUpdates) {
        if (line.size() / 2 <= maxUpdates) {
            return true
        };
        for (i in 0..line.size() / 2 ) {
            if (line[i] != line[-i-1] && maxUpdates-- == 0) {
                return false;
            }
        }
        return true;
    }

sun east replied on Sat, 2013/08/31 - 3:25am

scala> :paste
// Entering paste mode (ctrl-D to finish)

def verify(xs: Seq[Char], k: Int): Boolean = 
  (0 to xs.size/2).count{ i =>
    xs(i) != xs(xs.size - 1 - i)
  } <= k

// Exiting paste mode, now interpreting.

verify: (xs: Seq[Char], k: Int)Boolean

scala> verify("abbc", 0)
res0: Boolean = false

scala> verify("abbc", 1)
res1: Boolean = true

Abhilash Ponnachan replied on Sat, 2013/08/31 - 1:24pm

# *** Python ***
def is_k_pal(text, k = 0):
    for i in range(len(text) // 2):
        if text[i] != text[-i-1]:
            k-=1
        if k < 0:
            return False
    return True
print(is_k_pal("mannan", 1))    #True
print(is_k_pal("mannan", 0))    #False

Rafael Naufal replied on Tue, 2013/09/03 - 10:23am

Here is my Ruby solution: http://rafaelnaufal.com/blog/2013/09/03/k-palindromes-puzzle/

Ebrahim Rajabzadeh replied on Thu, 2013/09/05 - 11:45pm

def kpal s, k
    s.chars.zip(s.reverse.chars).map {|x, y| x==y}.count(false)/2 <= k
end

Arkadiusz Bicz replied on Wed, 2013/09/18 - 8:28am

  def palindromeK(p:Vector[Char], k:Int) : Boolean =
  {
    val (l,r) = (p.splitAt(math.ceil(p.size.toDouble/2.0).toInt))
    (l, r.reverse).zipped.filter(_ != _)._1.size <= k
  }

  assert(palindromeK("abccba".toVector,0))
  assert(palindromeK("abcacbc".toVector,1))
  assert(palindromeK("abbc".toVector,1))
  assert(!palindromeK("abgcc".toVector,1))

Charles Cartwright replied on Sat, 2013/09/21 - 6:22am


Luci Vuc replied on Mon, 2013/11/18 - 8:45pm

Hi. Assuming that a number of K characters in the string can be replaced with any other characters, here is a solution in Java:

import java.util.Scanner;

public class KPalindrome {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		String word = "";
		int k = 0;
		boolean b = true;
		while(true){
			System.out.print("Enter the word: ");
			word = scn.next();
			do{
				b = false;
				System.out.print("Enter the K value: ");
				try{
					k = scn.nextInt();
				}catch(Exception ex){
					b = true;
				}
			}while(b);
			
			System.out.printf("--= With K = %d, the word '%s' %s K Palindrome. =--\n", 
					k, word, isPalindrome(word, k-1)? "IS": "is NOT");
			
			System.out.print("Continue? y/n: ");
			if(!scn.next().equals("y")){
				break;
			}
		}
		scn.close();
		System.out.println("Bye");
	}

	// returns true if the given word is a K Palindrom (based on the given K), 
	// or false otherwise
	public static boolean isPalindrome(String word, int k){
		if(isPalindrome(word)){
			return true;
		}
		if(k >= word.length() / 2){
			k = word.length() / 2 - 1;
		}
		if(k < 0){
			return false;
		}
		char[] ch = word.toCharArray();
		ch[k] = word.charAt(word.length() - 1 - k);
		return isPalindrome(String.valueOf(ch), k - 1);
	}
	
	// returns true if the given word is palindrom, or false otherwise
	public static boolean isPalindrome(String word){
		for(int x = 0, mid = word.length() / 2; x < mid; x++){
			if(word.charAt(x) != word.charAt(word.length() - 1 - x)){
				return false;
			}
		}
		return true;
	}
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.