Check if line swapping can become a palindrome

Question

Write a method to check if a string meets the prerequisites to become a palindrome.

For instance:

Input | Output mmo | True yakak | True travel | False 

I think about this:

• Make a suffix tree for all permutations T such that T $ Reverse (T) #
• Check all permutations for the same node

Did I miss something?

Answer 1

Indeed, all you are looking for is if all (or all but one) of the letters are paired. As long as they are, then they can turn into a palindrome.

So that would be something like ...

 bool canBeTurnedIntoAPalindrome(string drome) { // If we've found a letter that has no match, the center letter. bool centerUsed = false; char center; char c; int count = 0; // TODO: Remove whitespace from the string. // Check each letter to see if there an even number of it. for(int i = 0; i<drome.length(); i++) { c = drome[i]; count = 0; for(int j = 0; j < drome.length(); j++) if (drome[j] == c) count++; // If there was an odd number of those entries // and the center is already used, then a palindrome // is impossible, so return false. if (count % 2 == 1) { if (centerUsed == true && center != c) return false; else { centerused = true; center = c; // This is so when we encounter it again it // doesn't count it as another separate center. } } } // If we made it all the way through that loop without returning false, then return true; } 

This is not the most efficient (it counts the letters as many times as it comes to them, even if they are already counted), but it works.

Answer 2

All you have to do is check that there is no more than one character with an odd number of occurrences. Here is a Java example:

 private static boolean canMakePalindrom(String s) { Map<Character, Integer> countChars = new HashMap<>(); // Count the occurrences of each character for (char c : s.toCharArray()) { Integer count = countChars.get(c); if (count == null) { count = Integer.valueOf(1); } else { count = count + 1; } countChars.put(c, count); } boolean hasOdd = false; for (int count : countChars.values()) { if (count % 2 == 1) { if (hasOdd) { // Found two chars with odd counts - return false; return false; } else { // Found the first char with odd count hasOdd = true; } } } // Haven't found more than one char with an odd count return true; } 

EDIT4 (yes - they are ordered to make sense, but are numbered in chronological order):
The above implementation has built-in inefficiency. I don’t think that the first iteration over the line can be avoided, but there is no real reason to count all occurrences - this is enough to just keep track of those who have an odd number. To do this, usecase is enough to track each character that we encounter (for example, using Set ), and delete it when we encounter it again. In the worst case, when all the characters in the string are different, the performance is comparable, but in the general case, when there are several occurrences of each character, this implementation improves the complexity of time and memory of the second cycle (which is now reduced to one condition):

 private static boolean canMakePalindrom(String s) { Set<Character> oddChars = new HashSet<>(); // Go over the characters for (char c : s.toCharArray()) { // Record the encountered character: if (!oddChars.add(c)) { // If the char was already encountered, remove it - // this is an even time we encounter it oddChars.remove(c); } } // Check the number of characters with odd counts: return oddChars.size() <= 1; } 

EDIT3 (yes - they are ordered to make sense, but are numbered in chronological order):
Java 8 provides a free streaming API that can be used to create an implementation similar to the one-line Python below:

 private static boolean canMakePalindrom(String s) { return s.chars() .boxed() .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) .values() .stream() .filter(p -> p % 2 == 1) .count() <= 1; } 

EDIT:
Python's built-in features and comprehension capabilities make it too attractive to not publish this one lineup solution. It is probably less efficient than the above Java, but pretty elegant:

 from collections import Counter def canMakePalindrom(s): return len([v for v in Counter(s).values() if v % 2 == 1]) <= 1 

EDIT2:
Or, a cleaner approach suggested by @DSM in the comments:

 from collections import Counter def canMakePalindrom(s): return sum(v % 2 == 1 for v in Counter(s).values()) <= 1 

Answer 3

Instead of counting how many times each letter occurs, a different approach keeps track of whether the letter occurred with an odd or even number of times. If the letter occurred exactly several times, you do not need to worry about this, and you only need to track the odd occurrences in the set. In Java:

 public static boolean canMakePalindrome(String s) { Set<Character> oddLetters = new HashSet<>(); for ( char c : s.toCharArray() ) { if ( ! oddLetters.remove(c) ) { oddLetters.add(c); } } return oddLetters.size() <= 1; } 

Answer 4

If I understand your question correctly, I understand:

If the input string can be rearranged into a palindrome, print "True", otherwise print "False".

Then you can use these simple rules:

• If the length is even, each unique character at the input must have a factor of 2.
• If the length is odd, each unique character, except for one, must be a multiple of 2 times. Only 1 character is allowed not to appear several times.

So, for 3 given examples:

"mmo", an odd length, m happens twice (a multiple of 2), o happens once (not a multiple of 2), so True .

"like", an odd length, a occurs twice (a multiple of 2), k occurs twice (several of two), y occurs once (not a multiple of 2), so True .

"travel", more than one character does not occur in multiples of 2, therefore False .

Additional examples:

"mmorpg", only m is a multiple of 2, the rest is only once, so False .

"mmom", no characters are found multiple of 2, more than one character is found "not multiple of 2 times", therefore False .

At this point, you should understand that if only 1 character is allowed, but not multiple, then you can ignore the length. An even-length string will have 2 or more characters that are not multiple, or not all.

So, the final rule should be as follows:

If no more than 1 unique character is found not in the plural-2 times at the input, the True output otherwise the output will be False .

Answer 5

 def can_permutation_palindrome(s): counter = {} for c in s: counter[c] = counter.get(c, 0) + 1 odd_count = 0 for count in counter.values(): odd_count += count % 2 return odd_count in [0, 1] 

Answer 6

 def check(string): bv = 0 for s in string: bv ^= 1 << ord(s) return bv == 0 or bv & (bv - 1) == 0 

Answer 7

You can save a space of letters in a string. If the result is 0, then all characters have a pair. If the result represents a character that exists in the string, then all letters have a pair but one.

Using this rule, we can determine if a permutation of a string is a palindrome:

 def can_be_palindrome(string): char_set = {} xor_result = 0 for c in string: if c not in char_set: char_set[c] = 1 xor_result ^= ord(c) return xor_result == 0 or chr(xor_result) in char_set 

Answer 8

My idea is that if the number of letters with an odd number is one and everyone else has an account, a palindrome is possible .. Here is my program in Python

 string = raw_input() found = False char_set = set(string) # Lets find unique letters d_dict = {} for c in char_set: d_dict[c] = string.count(c) # Keep count of each letter odd_l = [e for e in d_dict.values() if e%2 == 1] # Check how many has odd number of occurrence if len(odd_l) >1: pass else: found = True if not found: print("NO") else: print("YES") 

Answer 9

Any line can be a palindrome, only if no more than one character is found odd no. times and all other characters must occur exactly as many times. The following program can be used to check if the palindrome can be a string or not.

 void checkPalindrome(string s) { vector<int> vec(256,0); //Vector for all ASCII characters present. for(int i=0;i<s.length();++i) { vec[s[i]-'a']++; } int odd_count=0,flag=0; for(int i=0;i<vec.size();++i) { if(vec[i]%2!=0) odd_count++; if(odd_count>1) { flag=1; cout<<"Can't be palindrome"<<endl; break; } } if(flag==0) cout<<"Yes can be palindrome"<<endl; } 

Answer 10

With complexity O (n).

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace PallindromePemutation { class charcount { public char character { get; set; } public int occurences { get; set; } } class Program { static void Main(string[] args) { List<charcount> list = new List<charcount>(); charcount ch; int count = 0; char[] arr = "travel".ToCharArray(); for (int i = 0; i < arr.Length; i++) { charcount res = list.Find(x => x.character == arr.ElementAt(i)); if (res == null) { ch = new charcount(); ch.character = arr.ElementAt(i); ch.occurences = 1; list.Add(ch); } else { charcount temp= list.Find(x => x.character == arr.ElementAt(i)); temp.occurences++; } } foreach (var item in list) { if (!(item.occurences % 2 == 0)) { count++; } } if (count > 1) { Console.WriteLine("false"); } else { Console.WriteLine("true"); } Console.ReadKey(); } } } 

Answer 11

If we do not need case sensitivity of characters and spaces inside a string, then an approximate solution in C # using a dictionary can be as follows:

  private static bool IsPalindromePermutation(string inputStr) { // First, check whether input string is null or whitespace. // If yes, then return false. if (string.IsNullOrWhiteSpace(inputStr)) return false; var inputDict = new Dictionary<char, int>(); // Big/small letter is not important var lowerInputStr = inputStr.ToLower(); // Fill input dictionary // If hit a space, then skip it for (var i = 0; i < lowerInputStr.Length; i++) { if (lowerInputStr[i] != ' ') { if (inputDict.ContainsKey(lowerInputStr[i])) inputDict[lowerInputStr[i]] += 1; else inputDict.Add(lowerInputStr[i], 1); } } var countOdds = 0; foreach(var elem in inputDict) { if(elem.Value % 2 != 0) countOdds++; } return countOdds <= 1; } 

Answer 12

We can get it through collections as well.

 String name = "raa"; List<Character> temp = new ArrayList<>(name.chars() .mapToObj(e -> (char) e).collect(Collectors.toList())); for (int i = 0; i < temp.size(); i++) { for (int j = i + 1; j < temp.size(); j++) { if (temp.get(i).equals(temp.get(j))) { temp.remove(j); temp.remove(i); i--; } } } if (temp.size() <= 1) { System.out.println("Pallindrome"); } else { System.out.println(temp.size()); System.out.println("Not Pallindrome"); } } 

Answer 13

This is my decision

 public static void main(String[] args) { List<Character> characters = new ArrayList<>(); Scanner scanner = new Scanner(System.in); String input = scanner.nextLine(); for (int i = 0; i < input.length(); i++){ char val = input.charAt(i); if (characters.contains(val)){ characters.remove(characters.indexOf(val)); } else{ characters.add(val); } } if (characters.size() == 1 || characters.size() == 0){ System.out.print("Yes"); } else{ System.out.print("No"); } } 

Answer 14

This is my decision. A string can contain several words with spaces, for example, Input: Tact Coa Exit true Input: Tact Coa vvu Exit: false

 public static boolean checkForPalindrome(String str) { String strTrimmed = str.replaceAll(" ",""); System.out.println(strTrimmed); char[] str1 = strTrimmed.toCharArray(); for (int i = 0; i < str1.length; i++) { str1[i] = Character.toLowerCase(str1[i]); } Arrays.sort(str1); String result = new String(str1); System.out.println(result); int count = 0; for (int j = 0; j < str1.length; j += 2) { if (j != str1.length-1) { if (str1[j] != str1[j+1]) { count++; j++; } } else { count++; } } if (count > 1) return false; else return true; } 

Answer 15

I came up with a solution below today (python). I think it is readable, and in performance it is really good.

 sum(map(lambda x: word.count(x) % 2, set(word))) <= 1 

We basically count the number of occurrences of each character in the word string, getting the remainder of dividing by 2, summing them all up and checking to see if you have at most 1 of them.

The idea is that you need all characters to be conjugated, with the exception of potentially one (middle).