Split a string in equal parts such that all parts are palindromes

0 0 8 minutes read

Given a string str, the task is to split the string into minimum parts such that each part is of same length and each part is a palindrome. Print the required number of parts.

Examples:

Input: str = “civicbob”
Output: 8
“b”, “b”, “c”, “c”, “i”, “i”, “v” and “o” are the required partitions. “civic” and “bob” are also palindromes but they are not of equal length

Input: str = “noonpeep”
Output: 1

Approach:

Count the number of odd appearing characters and store it in countOdd.
Sum the frequencies of all the even occurring characters and store it in sumEven.
Since, no more than one odd frequency character can be a part of the same palindrome. So, if (sumEven / 2) % countOdd = 0 then the answer is countOdd as sumEven can be divided into countOdd parts.
Else, we can still divide the odd occurring characters into the palindrome pairs. For example, if the character a appears 3 times i.e. aaa then aa can be a part of some palindrome while leaving a as odd (without affecting the original frequency).

Below is the implementation of the above approach:

C++

// C++ implementation of the approach 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the frequency array 
// for the given string 
int* getFrequencies(string str) 
{ 
    static int freq[26] = { 0 };
 
    for (int i = 0; i < str.length(); i++) { 
        freq[str[i] - 'a']++; 
    } 
 
    return freq; 
} 
 
// Function to return the required count 
int countMinParts(string str) 
{ 
 
    int n = str.length(); 
    int *freq = getFrequencies(str); 
 
    vector<int> oddFreq, evenFreq;
 
    int i, sumEven = 0; 
 
    for (i = 0; i < 26; i++) { 
        if (freq[i] == 0) 
            continue; 
 
        // Add frequencies of the even appearing 
        // characters 
        if (freq[i] % 2 == 0) 
            evenFreq.push_back(freq[i]); 
 
        // Count of the characters that appeared 
        // odd number of times 
        else
            oddFreq.push_back(freq[i]); 
    } 
 
    for (i = 0; i < evenFreq.size(); i++) { 
        sumEven += evenFreq[i]; 
    } 
 
    // If there are no characters with odd frequency 
    if (oddFreq.size() == 0) 
        return 1; 
 
    // If there are no characters with even frequency 
    if (sumEven == 0) { 
 
        // Only a single character with odd frequency 
        if (oddFreq.size() == 1) 
            return 1; 
 
        // More than 1 character with odd frequency 
        // string isn't a palindrome 
        return 0; 
    } 
 
    i = 0; 
 
    // All odd appearing characters can also contribute to 
    // the even length palindrome if one character 
    // is removed from the frequency leaving it as even 
    while (i < oddFreq.size()) { 
 
        // If k palindromes are possible where k 
        // is the number of characters with odd frequency 
        if ((sumEven / 2) % oddFreq.size() == 0) 
            return oddFreq.size(); 
 
        // Current character can no longer be an element 
        // in a string other than the mid character 
        if (oddFreq[i] == 1) { 
            i++; 
            continue; 
        } 
 
        // If current character has odd frequency > 1 
        // take two characters which can be used in 
        // any of the parts 
        sumEven += 2; 
 
        // Update the frequency 
        oddFreq[i] = oddFreq[i] - 2; 
    } 
 
    // If not possible, then every character of the 
    // string will act as a separate palindrome 
    return n; 
} 
 
// Driver code 
int main() 
{
 
    string s = "noonpeep"; 
 
    cout<<countMinParts(s); 
} 

Java

// Java implementation of the approach
import java.util.*;
public class GFG {
 
    // Function to return the frequency array
    // for the given string
    static int[] getFrequencies(String str)
    {
        int freq[] = new int[26];
        for (int i = 0; i < str.length(); i++) {
            freq[str.charAt(i) - 'a']++;
        }
        return freq;
    }
 
    // Function to return the required count
    static int countMinParts(String str)
    {
 
        int n = str.length();
        int freq[] = getFrequencies(str);
        List<Integer> oddFreq = new ArrayList<>();
        List<Integer> evenFreq = new ArrayList<>();
 
        int i, sumEven = 0;
 
        for (i = 0; i < 26; i++) {
            if (freq[i] == 0)
                continue;
 
            // Add frequencies of the even appearing 
            // characters
            if (freq[i] % 2 == 0)
                evenFreq.add(freq[i]);
 
            // Count of the characters that appeared 
            // odd number of times
            else
                oddFreq.add(freq[i]);
        }
 
        for (i = 0; i < evenFreq.size(); i++) {
            sumEven += evenFreq.get(i);
        }
 
        // If there are no characters with odd frequency
        if (oddFreq.size() == 0)
            return 1;
 
        // If there are no characters with even frequency
        if (sumEven == 0) {
 
            // Only a single character with odd frequency
            if (oddFreq.size() == 1)
                return 1;
 
            // More than 1 character with odd frequency
            // string isn't a palindrome
            return 0;
        }
 
        i = 0;
 
        // All odd appearing characters can also contribute to
        // the even length palindrome if one character
        // is removed from the frequency leaving it as even
        while (i < oddFreq.size()) {
 
            // If k palindromes are possible where k
            // is the number of characters with odd frequency
            if ((sumEven / 2) % oddFreq.size() == 0)
                return oddFreq.size();
 
            // Current character can no longer be an element
            // in a string other than the mid character
            if (oddFreq.get(i) == 1) {
                i++;
                continue;
            }
 
            // If current character has odd frequency > 1
            // take two characters which can be used in
            // any of the parts
            sumEven += 2;
 
            // Update the frequency
            oddFreq.set(i, oddFreq.get(i) - 2);
        }
 
        // If not possible, then every character of the 
        // string will act as a separate palindrome
        return n;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        String s = "noonpeep";
 
        System.out.println(countMinParts(s));
    }
}
 
// This code is contributed by chitranayal

Python3

# Python3 implementation of the approach 
 
# Function to return the frequency array 
# for the given string 
def getFrequencies(string) :
        freq = [0] * 26
 
        for i in range(len(string)) :
                freq[ord(string[i]) -
                     ord('a')] += 1
 
        return freq
 
# Function to return the required count 
def countMinParts(string) :
        n = len(string)
        freq = getFrequencies(string)
        oddFreq = []
        evenFreq = []
 
        sumEven = 0
 
        for i in range(26) :
 
                if freq[i] == 0 :
                    continue
 
                # Add frequencies of the even 
                # appearing characters 
                if freq[i] % 2 == 0 :
                        evenFreq.append(freq[i])
 
                # Count of the characters that 
                # appeared odd number of times
                else :
                        oddFreq.append(freq[i])
 
        for i in range(len(evenFreq)) :
                sumEven += evenFreq[i]
 
        # If there are no characters with
        # odd frequency 
        if len(oddFreq) == 0 :
                return 1
 
        # If there are no characters with 
        # even frequency
        if sumEven == 0 :
 
                # Only a single character with
                # odd frequency
                if len(oddFreq) == 1:
                        return 1
 
                # More than 1 character with odd 
                # frequency string isn't a palindrome 
                return 0
 
        i = 0
 
        # All odd appearing characters can also 
        # contribute to the even length palindrome 
        # if one character is removed from the 
        # frequency leaving it as even
        while(i < len(oddFreq)) :
                 
                # If k palindromes are possible where 
                # k is the number of characters with 
                # odd frequency 
                if ((sumEven / 2) % len(oddFreq) == 0) :
                        return len(oddFreq)
 
                # Current character can no longer be 
                # an element in a string other than
                # the mid character 
                if (oddFreq[i] == 1) :
                        i += 1
                        continue
 
                # If current character has odd frequency > 1 
                # take two characters which can be used in 
                # any of the parts 
                sumEven += 2
 
                # Update the frequency
                oddFreq[i] = oddFreq[i] - 2
 
        # If not possible, then every character of the 
        # string will act as a separate palindrome 
        return n
 
# Driver code
if __name__ == "__main__" :
 
    s = "noonpeep"
 
    print(countMinParts(s))
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to return the frequency array
    // for the given string
    static int[] getFrequencies(String str)
    {
        int []freq = new int[26];
        for (int i = 0; i < str.Length; i++) 
        {
            freq[str[i] - 'a']++;
        }
        return freq;
    }
 
    // Function to return the required count
    static int countMinParts(String str)
    {
 
        int n = str.Length;
        int []freq = getFrequencies(str);
        List<int> oddFreq = new List<int>();
        List<int> evenFreq = new List<int>();
 
        int i, sumEven = 0;
 
        for (i = 0; i < 26; i++)
        {
            if (freq[i] == 0)
                continue;
 
            // Add frequencies of the even appearing 
            // characters
            if (freq[i] % 2 == 0)
                evenFreq.Add(freq[i]);
 
            // Count of the characters that appeared 
            // odd number of times
            else
                oddFreq.Add(freq[i]);
        }
 
        for (i = 0; i < evenFreq.Count; i++)
        {
            sumEven += evenFreq[i];
        }
 
        // If there are no characters with odd frequency
        if (oddFreq.Count == 0)
            return 1;
 
        // If there are no characters with even frequency
        if (sumEven == 0)
        {
 
            // Only a single character with odd frequency
            if (oddFreq.Count == 1)
                return 1;
 
            // More than 1 character with odd frequency
            // string isn't a palindrome
            return 0;
        }
 
        i = 0;
 
        // All odd appearing characters can also contribute to
        // the even length palindrome if one character
        // is removed from the frequency leaving it as even
        while (i < oddFreq.Count)
        {
 
            // If k palindromes are possible where k
            // is the number of characters with odd frequency
            if ((sumEven / 2) % oddFreq.Count == 0)
                return oddFreq.Count;
 
            // Current character can no longer be an element
            // in a string other than the mid character
            if (oddFreq[i] == 1) 
            {
                i++;
                continue;
            }
 
            // If current character has odd frequency > 1
            // take two characters which can be used in
            // any of the parts
            sumEven += 2;
 
            // Update the frequency
            oddFreq.Insert(i, oddFreq[i] - 2);
        }
 
        // If not possible, then every character of the 
        // string will act as a separate palindrome
        return n;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
 
        String s = "noonpeep";
 
        Console.WriteLine(countMinParts(s));
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the frequency array
    // for the given string
function getFrequencies(str)
{
    let freq = new Array(26);
    for(let i=0;i<26;i++)
        freq[i]=0;
        for (let i = 0; i < str.length; i++) {
            freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        return freq;
}
 
// Function to return the required count
function countMinParts(str)
{
        let n = str.length;
        let freq = getFrequencies(str);
        let oddFreq = [];
        let evenFreq = [];
   
        let i, sumEven = 0;
   
        for (i = 0; i < 26; i++) {
            if (freq[i] == 0)
                continue;
   
            // Add frequencies of the even appearing 
            // characters
            if (freq[i] % 2 == 0)
                evenFreq.push(freq[i]);
   
            // Count of the characters that appeared 
            // odd number of times
            else
                oddFreq.push(freq[i]);
        }
   
        for (i = 0; i < evenFreq.length; i++) {
            sumEven += evenFreq[i];
        }
   
        // If there are no characters with odd frequency
        if (oddFreq.length == 0)
            return 1;
   
        // If there are no characters with even frequency
        if (sumEven == 0) {
   
            // Only a single character with odd frequency
            if (oddFreq.length == 1)
                return 1;
   
            // More than 1 character with odd frequency
            // string isn't a palindrome
            return 0;
        }
   
        i = 0;
   
        // All odd appearing characters can also contribute to
        // the even length palindrome if one character
        // is removed from the frequency leaving it as even
        while (i < oddFreq.length) {
   
            // If k palindromes are possible where k
            // is the number of characters with odd frequency
            if ((sumEven / 2) % oddFreq.length == 0)
                return oddFreq.length;
   
            // Current character can no longer be an element
            // in a string other than the mid character
            if (oddFreq[i] == 1) {
                i++;
                continue;
            }
   
            // If current character has odd frequency > 1
            // take two characters which can be used in
            // any of the parts
            sumEven += 2;
   
            // Update the frequency
            oddFreq[i]= oddFreq[i] - 2;
        }
   
        // If not possible, then every character of the 
        // string will act as a separate palindrome
        return n;
}
 
 // Driver code
let s = "noonpeep";
 
document.write(countMinParts(s));
 
// This code is contributed by rag2127
 
</script>

Output

Time complexity: O(n) where n is the length of the given string
Auxiliary space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!