Given palindromic string s, the task is to find minimum k, such that you can cut this string into k+1 parts, and then unite them in such a way that the final string will be a palindrome and it won’t be equal to the initial string s. If it is impossible then print -1.
Examples:
Input : string = "civic" Output : 2 Explanation : ci | v | ic --> ic | v | ci --> icvci Input : string = "gggg" Output : -1 Input : string = "redder" Output : 1 Explanation : red | der --> der | red --> derred Input : string = "aaaasaaaa" Output : -1
Approach 1: It is given that formed palindromic string should be different from the given string.
So when our string consists of n or n-1 (when n is odd) equal characters, then there is no way to get the answer. For example –
String : "aaaasaaaa" String : "aaaa"
Above strings can not form palindrome other than the given one.
Otherwise, cut the longest prefix of s of length l, that consists of equal characters of length equal to l-1. Now similarly cut suffix of length l-1, and call remaining part as mid.
Now we have prefix = s[1..l] and suff = s[(n-l+1)..n]. Swap prefix and suffix, then unite all three parts together and keep mid as it is.
prefix + mid + suffix[Tex]suffix + mid + prefix[/Tex]
[Tex]suffix + mid + prefix[/Tex]So clearly we can get the answer in two cuts. Finally you just have to check if it is possible to get answer in one cut. For that just cut one element from end and append it at front and continue this cyclic shift. During this if we get a palindromic string other then the given one then it means we can get answer in just one cut.
Below is the implementation of above approach:
C++
// CPP program to solve the above problem#include <bits/stdc++.h>using namespace std;// Function to check if string is palindrome or notbool isPalindrome(string s){ for (int i = 0; i < s.length(); ++i) { if (s[i] != s[s.length() - i - 1]) { return false; } } return true;}// Function to check if it is possible to// get result by making just one cutbool ans(string s){ string s2 = s; for (int i = 0; i < s.length(); ++i) { // Appending last element in front s2 = s2.back() + s2; // Removing last element s2.pop_back(); // Checking whether string s2 is palindrome // and different from s. if (s != s2 && isPalindrome(s2)) { return true; } } return false;}int solve(string s){ // If length is <=3 then it is impossible if (s.length() <= 3) { return -1; } // Array to store frequency of characters int cnt[25] = {}; // Store count of characters in a array for (int i = 0; i < s.length(); i++) { cnt[s[i] - 'a']++; } // Condition for edge cases if (*max_element(cnt, cnt + 25) >= (s.length() - 1)) { return -1; } else { // Return 1 if it is possible to get palindromic // string in just one cut. // Else we can always reached in two cuttings. return (ans(s) ? 1 : 2); }}// Driver Codeint main(){ string s = "nolon"; cout << solve(s); return 0;} |
Java
// Java program to solve the above problemimport java.util.Arrays;class GFG{// Function to check if string is palindrome or notstatic boolean isPalindrome(String s){ for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) != s.charAt(s.length() - i - 1)) { return false; } } return true;}// Function to check if it is possible to// get result by making just one cutstatic boolean ans(String s){ String s2 = s; for (int i = 0; i < s.length(); ++i) { // Appending last element in front s2 = s2.charAt(s2.length()-1) + s2; // Removing last element s2 = s2.substring(0,s2.length()-1); // Checking whether string s2 is palindrome // and different from s. if ((s == null ? s2 != null : !s.equals(s2)) && isPalindrome(s2)) { return true; } } return false;}static int solve(String s){ // If length is <=3 then it is impossible if (s.length() <= 3) { return -1; } // Array to store frequency of characters int cnt[] = new int[25]; // Store count of characters in a array for (int i = 0; i < s.length(); i++) { cnt[s.charAt(i) - 'a']++; } // Condition for edge cases if (Arrays.stream(cnt).max().getAsInt() >= (s.length() - 1)) { return -1; } else { // Return 1 if it is possible to get palindromic // string in just one cut. // Else we can always reached in two cuttings. return (ans(s) ? 1 : 2); }}// Driver Codepublic static void main(String[] args) { String s = "nolon"; System.out.println(solve(s)); }}// This code contributed by Rajput-Ji |
Python3
# Python 3 program to solve the above problem# Function to check if string is palindrome or notdef isPalindrome(s): for i in range(len(s)): if (s[i] != s[len(s) - i - 1]): return False return true# Function to check if it is possible to# get result by making just one cutdef ans(s): s2 = s for i in range(len(s)): # Appending last element in front s2 = s2[len(s2) - 1] + s2 # Removing last element s2 = s2[0:len(s2) - 1] # Checking whether string s2 is palindrome # and different from s. if (s != s2 and isPalindrome(s2)): return True return Falsedef solve(s): # If length is <=3 then it is impossible if (len(s) <= 3): return -1 # Array to store frequency of characters cnt = [0 for i in range(26)] # Store count of characters in a array for i in range(len(s)): cnt[ord(s[i]) - ord('a')] += 1 # Condition for edge cases max = cnt[0] for i in range(len(cnt)): if cnt[i]>max: max = cnt[i] if (max >= len(s) - 1): return -1 else: # Return 1 if it is possible to get # palindromic string in just one cut. # Else we can always reached in two cuttings. if ans(s) == True: return 1 else: return 2# Driver Codeif __name__ == '__main__': s = "nolon" print(solve(s)) # This code is contributed by# Surendra_Gangwar |
C#
// C# program to solve the above problemusing System;using System.Linq;class GFG{// Function to check if string is palindrome or notstatic bool isPalindrome(string s){ for (int i = 0; i < s.Length; ++i) { if (s[i] != s[s.Length - i - 1]) { return false; } } return true;}// Function to check if it is possible to// get result by making just one cutstatic bool ans(string s){ string s2 = s; for (int i = 0; i < s.Length; ++i) { // Appending last element in front s2 = s2[s2.Length-1] + s2; // Removing last element s2 = s2.Substring(0,s2.Length-1); // Checking whether string s2 is palindrome // and different from s. if ((s == null ? s2 != null : !s.Equals(s2)) && isPalindrome(s2)) { return true; } } return false;}static int solve(string s){ // If length is <=3 then it is impossible if (s.Length <= 3) { return -1; } // Array to store frequency of characters int[] cnt = new int[25]; // Store count of characters in a array for (int i = 0; i < s.Length; i++) { cnt[s[i] - 'a']++; } // Condition for edge cases if (cnt.Max() >=(s.Length - 1)) { return -1; } else { // Return 1 if it is possible to get palindromic // string in just one cut. // Else we can always reached in two cuttings. return (ans(s) ? 1 : 2); }}// Driver Codestatic void Main() { string s = "nolon"; Console.WriteLine(solve(s));}}// This code contributed by mits |
Javascript
<script>// JavaScript program to solve the above problem// Function to check if string is palindrome or notfunction isPalindrome(s){ for (let i = 0; i < s.length; ++i) { if (s[i] != s[s.length - i - 1]) { return false; } } return true;}// Function to check if it is possible to// get result by making just one cutfunction ans(s){ let s2 = s; for (let i = 0; i < s.length; ++i) { // Appending last element in front s2 = s2[s2.length-1] + s2; // Removing last element s2 = s2.substring(0,s2.length-1); // Checking whether string s2 is palindrome // and different from s. if ((s == null ? s2 != null : !s == (s2)) && isPalindrome(s2)) { return true; } } return false;}function solve(s){ // If length is <=3 then it is impossible if (s.length <= 3) { return -1; } // Array to store frequency of characters let cnt = new Array(25); for(let i=0;i<25;i++) cnt[i]=0; // Store count of characters in a array for (let i = 0; i < s.length; i++) { cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Condition for edge cases if (Math.max(...cnt) >= (s.length - 1)) { return -1; } else { // Return 1 if it is possible to get palindromic // string in just one cut. // Else we can always reached in two cuttings. return (ans(s) ? 1 : 2); }}// Driver Codelet s = "nolon";document.write(solve(s));// This code is contributed by rag2127</script> |
Output:
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: Again if our string consists of n or n-1 (when n is odd) equal characters, then there is no way to get the answer.
Now, divide this problem into two parts that whether the string length is even or odd.
If the string length is odd then we always have a middle element in it so just make 2 cuts around the middle element and split the string into three segments and swap first and third segments.
Say, we have a string:
nolon --> no | l | on --> on | l | no --> onlno
If the string length is even then check whether the half string is itself a palindromic string or not.
If so then:
- Split a string recursively into two parts and check whether the resulting half string is a palindrome or not.
- If string became of odd length then simply return 2.
asaasa --> as | aa | sa --> sa | aa | as --> saaaas
- If resulting string is not a palindrome then return 1.
toottoot --> to | ottoot --> ottoot | to --> ottootto
Else we can cut this string from the middle, form two segments and swap each other.
For Example:
voov --> vo | ov --> ov | vo --> ovvo
Below is the implementation of above approach:
C++
// CPP program to solve the above problem#include <bits/stdc++.h>using namespace std;// Recursive function to find minimum number // of cuts if length of string is evenint solveEven(string s){ // If length is odd then return 2 if (s.length() % 2 == 1) return 2; // To check if half of palindromic string // is itself a palindrome string ls = s.substr(0, s.length() / 2); string rs = s.substr(s.length() / 2, s.length()); // If not then return 1 if (ls != rs) return 1; // Else call function with half palindromic string return solveEven(ls);}// Function to find minimum number of cuts// If length of string is oddint solveOdd(string s){ return 2;}int solve(string s){ // If length is <=3 then it is impossible if (s.length() <= 3) { return -1; } // Array to store frequency of characters int cnt[25] = {}; // Store count of characters in a array for (int i = 0; i < s.length(); i++) { cnt[s[i] - 'a']++; } // Condition for edge cases if (*max_element(cnt, cnt + 25) >= s.length() - 1) { return -1; } // If length is even if (s.length() % 2 == 0) return solveEven(s); // If length is odd if (s.length() % 2 == 1) return solveOdd(s);}// Driver Codeint main(){ string s = "nolon"; cout << solve(s); return 0;} |
Java
// Java program to solve the above problem import java.util.Arrays;class GFG { // Recursive function to find minimum number // of cuts if length of String is even static int solveEven(String s) { // If length is odd then return 2 if (s.length() % 2 == 1) { return 2; } // To check if half of palindromic String // is itself a palindrome String ls = s.substring(0, s.length() / 2); String rs = s.substring(s.length() / 2, s.length()); // If not then return 1 if (ls != rs) { return 1; } // Else call function with half palindromic String return solveEven(ls); } // Function to find minimum number of cuts // If length of String is odd static int solveOdd(String s) { return 2; } static int solve(String s) { // If length is <=3 then it is impossible if (s.length() <= 3) { return -1; } // Array to store frequency of characters int cnt[] = new int[25]; // Store count of characters in a array for (int i = 0; i < s.length(); i++) { cnt[s.charAt(i) - 'a']++; } // Condition for edge cases if (Arrays.stream(cnt).max().getAsInt() >= s.length() - 1) { return -1; } // If length is even if (s.length() % 2 == 0) { return solveEven(s); } // If length is odd if (s.length() % 2 == 1) { return solveOdd(s); } return Integer.MIN_VALUE; } // Driver Code public static void main(String[] args) { String s = "nolon"; System.out.println(solve(s)); }}// This code has been contributed by 29AjayKumar |
Python3
# Python3 program to solve the above problem # Recursive function to find minimum number # of cuts if length of string is even def solveEven(s): # If length is odd then return 2 if len(s) % 2 == 1: return 2 # To check if half of palindromic # string is itself a palindrome ls = s[0 : len(s) // 2] rs = s[len(s) // 2 : len(s)] # If not then return 1 if ls != rs: return 1 # Else call function with # half palindromic string return solveEven(ls) # Function to find minimum number of cuts # If length of string is odd def solveOdd(s): return 2def solve(s): # If length is <=3 then it is impossible if len(s) <= 3: return -1 # Array to store frequency of characters cnt = [0] * 25 # Store count of characters in a array for i in range(0, len(s)): cnt[ord(s[i]) - ord('a')] += 1 # Condition for edge cases if max(cnt) >= len(s) - 1: return -1 # If length is even if len(s) % 2 == 0: return solveEven(s) # If length is odd if len(s) % 2 == 1: return solveOdd(s) # Driver Code if __name__ == "__main__": s = "nolon" print(solve(s)) # This code is contributed by Rituraj Jain |
C#
// C# program to solve the above problemusing System;using System.Linq;class GFG { // Recursive function to find minimum number // of cuts if length of String is even static int solveEven(String s) { // If length is odd then return 2 if (s.Length % 2 == 1) { return 2; } // To check if half of palindromic String // is itself a palindrome String ls = s.Substring(0, s.Length / 2); String rs = s.Substring(s.Length / 2, s.Length); // If not then return 1 if (ls != rs) { return 1; } // Else call function with half palindromic String return solveEven(ls); } // Function to find minimum number of cuts // If length of String is odd static int solveOdd(String s) { return 2; } static int solve(String s) { // If length is <=3 then it is impossible if (s.Length <= 3) { return -1; } // Array to store frequency of characters int []cnt = new int[25]; // Store count of characters in a array for (int i = 0; i < s.Length; i++) { cnt[s[i] - 'a']++; } // Condition for edge cases if (cnt.Max() >= s.Length - 1) { return -1; } // If length is even if (s.Length % 2 == 0) { return solveEven(s); } // If length is odd if (s.Length % 2 == 1) { return solveOdd(s); } return int.MinValue; } // Driver Code public static void Main() { String s = "nolon"; Console.WriteLine(solve(s)); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript program to solve the above problem// Recursive function to find minimum number // of cuts if length of String is evenfunction solveEven(s){ // If length is odd then return 2 if (s.length % 2 == 1) { return 2; } // To check if half of palindromic String // is itself a palindrome let ls = s.substring(0, s.length / 2); let rs = s.substring(s.length / 2, s.length); // If not then return 1 if (ls != rs) { return 1; } // Else call function with half palindromic String return solveEven(ls);}// Function to find minimum number of cuts // If length of String is oddfunction solveOdd(s){ return 2;}function solve(s){ // If length is <=3 then it is impossible if (s.length <= 3) { return -1; } // Array to store frequency of characters let cnt = new Array(25); for(let i=0;i<25;i++) cnt[i]=0; // Store count of characters in a array for (let i = 0; i < s.length; i++) { cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Condition for edge cases if (Math.max(...cnt) >= s.length - 1) { return -1; } // If length is even if (s.length % 2 == 0) { return solveEven(s); } // If length is odd if (s.length % 2 == 1) { return solveOdd(s); } return Number.MIN_VALUE;}// Driver Codelet s = "nolon";document.write(solve(s));// This code is contributed by avanitrachhadiya2155</script> |
Output:
2
Time Complexity : O(N)
Auxiliary Space: O(max(26,N))
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
