Solution: Palindrome Permutation

Let's solve the Palindrome Permutation problem using the Knowing What to Track pattern.

We'll cover the following

Statement
Solution
- Naive approach
- Optimized approach using frequency counting

Statement

For a given string, st, find whether or not a permutation of this string is a palindromePalindrome is a string of characters that reads the same forwards and backwards. For example, “ababa” and “xyxxyx” are palindromes.. You should return TRUE if such a permutation is possible and FALSE if it isn’t possible.

Constraints:

$1 \leq$ st.length $\leq 1000$
The string will contain lowercase English letters.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive solution is to first compute all possible permutations of a given string and then iterate over each permutation to see if it’s a palindrome. We can use two pointers to traverse the computed permutation from the beginning and the end simultaneously, comparing each character at every step. If the two pointers point to the same character until they cross each other, the string is a palindrome.

The number of possible permutations for a string of length $n$ is $n!$ , and it requires iterating through the $n$ characters to construct each permutation. Therefore, it will take $O(n! \times n)$ time to generate all these permutations. Then, for each permutation, we need to check whether it is a palindrome. Checking this condition requires iterating through the permutation once, which takes $O(n)$ time. Therefore, the overall time complexity of this naive approach is $O((n! \times n)\times n)$ . The space complexity is $O(n!)$ because we need to store all the permutations.

Optimized approach using frequency counting

This is the stereotypical example of a problem whose naive solution is very inefficient, yet by identifying a few key properties of the problem, we are able to devise a solution with superior time and space complexity measures. In this case, there are three key observations:

In a palindrome of even length, all the characters occur an even number of times. For example, in the palindrome “aaaabbaaaa”, “a” occurs four times and “b” occurs twice.
In a palindrome of odd length, the character in the middle of the string appears once, and all the others occur an even number of times. For example, in the palindrome “aaabaaa”, “a” occurs six times and “b” occurs once.
The observations above are true for all the permutations of a palindrome. For example, “aaaaaaaabb” is a permutation of “aaaabbaaaa” in which “a” still occurs four times and “b” occurs twice.

So, to decide whether or not a given string has a permutation that is a palindrome, all we need to do is count the number of times each character appears in it and then check how many characters appear an odd number of times.

If no characters appear an odd number of times, then the string is of even length and has a permutation that is a palindrome.
If only one character appears an odd number of times, then the string is of odd length and has a permutation that is a palindrome.
If more than one character appears an odd number of times, then the string does not have a permutation that is a palindrome.

The slides below illustrate the working of our proposed solution:

class PalindromePermutation {
  public static String printArrayWithMarkers(String arr, int pvalue) {
    String out = "";
    for (int i = 0; i < pvalue; i++) {
      out += arr.charAt(i);
    }
    out += "«" + arr.charAt(pvalue) + "»";
    for (int i = pvalue + 1; i < arr.length(); i++) {
      out += arr.charAt(i);
    }
    return out;
  }
  public static boolean permutePalindrome(String st) {
    // Create a hashmap to keep track of the characters and their occurrences
    System.out.println("\n\tPopulating the hashmap");
    HashMap < Character,Integer > frequencies = new HashMap < Character,Integer > ();
    int index = 0;
    for (int i = 0; i < st.length(); i++) {
      System.out.println("\t\t" + printArrayWithMarkers(st, index));
      index += 1;
      System.out.println("\t\tCharacter: " + st.charAt(i));
      System.out.println("\t\tHashmap: " + frequencies);
      if (frequencies.containsKey(st.charAt(i))) {
        System.out.println("\t\t\t" + st.charAt(i) + " is already present in the hashmap");
        System.out.print("\t\t\tUpdating its frequency  ⟶ ");
        frequencies.put(st.charAt(i), frequencies.get(st.charAt(i)) + 1);
        System.out.println(frequencies + "\n");
      }
      else {
        System.out.println("\t\t\t" + st.charAt(i) + " is not present in the hashmap");
        System.out.print("\t\t\tSetting its frequency = 1  ⟶ ");
        frequencies.put(st.charAt(i), 1);
        System.out.println(frequencies + "\n");
      }
    }
    return false;
  }
  
  public static void main(String args[]) {
    List < String > strArray = Arrays.asList("baefeab", "abc", "xzz", "jjadd", "kllk");
    for (int i = 0; i < strArray.size(); i++) {
      System.out.println(i + 1 + ".\tInput string: " + strArray.get(i));
      boolean result = permutePalindrome(strArray.get(i));
      if (result) System.out.println("\n\tInput string has permutations that are palindromes");
      else System.out.println("\n\tInput string does not have a permutation that's a palindrome");
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}

Populating the hash map

class PalindromePermutation {
  public static String printArrayWithMarkers(String arr, int pvalue) {
    String out = "";
    for (int i = 0; i < pvalue; i++) {
      out += arr.charAt(i);
    }
    out += "«" + arr.charAt(pvalue) + "»";
    for (int i = pvalue + 1; i < arr.length(); i++) {
      out += arr.charAt(i);
    }
    return out;
  }
  public static boolean permutePalindrome(String st) {
    // Create a hashmap to keep track of the characters and their occurrences
    System.out.println("\n\tPopulating the hashmap");
    HashMap < Character,Integer > frequencies = new HashMap < Character,Integer > ();
    int index = 0;
    for (int i = 0; i < st.length(); i++) {
      System.out.println("\t\t" + printArrayWithMarkers(st, index));
      index += 1;
      System.out.println("\t\tCharacter: " + st.charAt(i));
      System.out.println("\t\tHashmap: " + frequencies);
      if (frequencies.containsKey(st.charAt(i))) {
        System.out.println("\t\t\t" + st.charAt(i) + " is already present in the hashmap");
        System.out.print("\t\t\tUpdating its frequency  ⟶ ");
        frequencies.put(st.charAt(i), frequencies.get(st.charAt(i)) + 1);
        System.out.println(frequencies + "\n");
      }
      else {
        System.out.println("\t\t\t" + st.charAt(i) + " is not present in the hashmap");
        System.out.print("\t\t\tSetting its frequency = 1  ⟶ ");
        frequencies.put(st.charAt(i), 1);
        System.out.println(frequencies + "\n");
      }
    }
    // Traverse the hashmap and update the count by 1, whenever a
    // character with odd number of occurences is found.
    int count = 0;
    System.out.println("\n\tCounting the characters with odd frequencies");
    System.out.println("\t\tHash map: " + frequencies);
    System.out.println("\t\tCount = " + count);
    for (Character ch: frequencies.keySet()) {
      System.out.println("\t\tFrequency of '" + ch + "' = " + frequencies.get(ch));
      if (frequencies.get(ch) % 2 != 0) {
        System.out.println("\t\t\tIncrementing count: " + count + " + 1 = " + (count + 1));
        count += 1;
      }
      else System.out.println("\t\t\tFrequency is not odd, moving to the next character\n");
    }
    return false;
  }
  
  public static void main(String args[]) {
    List < String > strArray = Arrays.asList("baefeab", "abc", "xzz", "jjadd", "kllk");
    for (int i = 0; i < strArray.size(); i++) {
      System.out.println(i + 1 + ".\tInput string: " + strArray.get(i));
      boolean result = permutePalindrome(strArray.get(i));
      if (result) System.out.println("\n\tInput string has permutations that are palindromes");
      else System.out.println("\n\tInput string does not have a permutation that's a palindrome");
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}

Counting the numbers

class PalindromePermutation {
  
  public static String printArrayWithMarkers(String arr, int pvalue) {
    String out = "";
    for (int i = 0; i < pvalue; i++) {
      out += arr.charAt(i);
    }
    out += "«" + arr.charAt(pvalue) + "»";
    for (int i = pvalue + 1; i < arr.length(); i++) {
      out += arr.charAt(i);
    }
    return out;
  }
  public static boolean permutePalindrome(String st) {
    // Create a hashmap to keep track of the characters and their occurrences
    System.out.println("\n\tPopulating the hashmap");
    HashMap < Character,Integer > frequencies = new HashMap < Character,Integer > ();
    int index = 0;
    for (int i = 0; i < st.length(); i++) {
      System.out.println("\t\t" + printArrayWithMarkers(st, index));
      index += 1;
      System.out.println("\t\tCharacter: " + st.charAt(i));
      System.out.println("\t\tHashmap: " + frequencies);
      if (frequencies.containsKey(st.charAt(i))) {
        System.out.println("\t\t\t" + st.charAt(i) + " is already present in the hashmap");
        System.out.print("\t\t\tUpdating its frequency  ⟶ ");
        frequencies.put(st.charAt(i), frequencies.get(st.charAt(i)) + 1);
        System.out.println(frequencies + "\n");
      }
      else {
        System.out.println("\t\t\t" + st.charAt(i) + " is not present in the hashmap");
        System.out.print("\t\t\tSetting its frequency = 1  ⟶ ");
        frequencies.put(st.charAt(i), 1);
        System.out.println(frequencies + "\n");
      }
    }
    // Traverse the hashmap and update the count by 1, whenever a
    // character with odd number of occurences is found.
    int count = 0;
    System.out.println("\n\tCounting the characters with odd frequencies");
    System.out.println("\t\tHash map: " + frequencies);
    System.out.println("\t\tCount = " + count);
    for (Character ch: frequencies.keySet()) {
      System.out.println("\t\tFrequency of '" + ch + "' = " + frequencies.get(ch));
      if (frequencies.get(ch) % 2 != 0) {
        System.out.println("\t\t\tIncrementing count: " + count + " + 1 = " + (count + 1));
        count += 1;
      }
      else System.out.println("\t\t\tFrequency is not odd, moving to the next character\n");
    }
    // If the count is smaller than or equal to 1 then the permutation exists,
    // otherwise does not
    System.out.println("\n\tCount: " + count);
    if (count <= 1) {
      System.out.println("\tCount is <= 1, return TRUE");
      return true;
    }
    else {
      System.out.println("\tCount > 1, returning FALSE");
      return false;
    }
  }
  public static void main(String args[]) {
    List < String > strArray = Arrays.asList("baefeab", "abc", "xzz", "jjadd", "kllk");
    for (int i = 0; i < strArray.size(); i++) {
      System.out.println(i + 1 + ".\tInput string: " + strArray.get(i));
      boolean result = permutePalindrome(strArray.get(i));
      if (result) System.out.println("\n\tInput string has permutations that are palindromes");
      else System.out.println("\n\tInput string does not have a permutation that's a palindrome");
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}

Palindrome Permutation

class PalindromePermutation {
  
  public static boolean permutePalindrome(String st) {
    
    HashMap < Character,Integer > frequencies = new HashMap < Character,Integer > ();
    for (int i = 0; i < st.length(); i++) {
      if (frequencies.containsKey(st.charAt(i))) {
        frequencies.put(st.charAt(i), frequencies.get(st.charAt(i)) + 1);
      }
      else {
        frequencies.put(st.charAt(i), 1);
      }
    }
  
    int count = 0;
    for (Character ch: frequencies.keySet()) {
      if (frequencies.get(ch) % 2 != 0) {
        count += 1;
      }
    }
    if (count <= 1) {
      return true;
    }
    else {
      return false;
    }
  }
  public static void main(String args[]) {
    List < String > strArray = Arrays.asList("baefeab", "abc", "xzz", "jjadd", "kllk");
    for (int i = 0; i < strArray.size(); i++) {
      System.out.println(i + 1 + ".\tInput string: " + strArray.get(i));
      boolean result = permutePalindrome(strArray.get(i));
      if (result) System.out.println("\n\tInput string has permutations that are palindromes");
      else System.out.println("\n\tInput string does not have a permutation that's a palindrome");
      System.out.println(PrintHyphens.repeat("-", 100));
    }
  }
}

Palindrome Permutation

Solution summary

To recap, the solution to this problem can be divided into the following parts:

Populate a hash map with string characters and their frequencies.
Count the number of characters with an odd frequency.
If the count of characters with an odd frequency exceeds $1$ , return FALSE. Otherwise, return TRUE.

Time complexity

There are two parts in this solution. In the first part, we iterate over a string of $n$ characters, checking their presence in a hash map and adding/updating the hash map as we go. The average time complexity for looking up values in a hash map is $O(1)$ . The worst case time complexity for looking up values in a hash map is $O(k)$ , where $k$ is the number of elements in the hash map. Since the string only contains lowercase English letters, there are $26$ distinct characters in this case.

Thus, the average time complexity of the first part of the solution is $O(n)$ while the worst case time complexity is $O(n \times k)$ . In this scenario, the worst case time complexity is $O(26 \times n)$ , which simplifies to $O(n)$ .

In the second part, our loop iterates at most $26$ times. Hence, the time complexity of the second part is $O(1)$ .

In summary, our solution’s average and worst case time complexity is $O(n)$ .

Space complexity

The hash map can grow up to $n$ if all the characters in the string are distinct. However, the number of distinct characters is bounded, and so is the space complexity. So, the space complexity is $O(1)$ .

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion