Minimum cuts required to convert a palindromic string to a different palindromic string

0 0 12 minutes read

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]

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 not
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 cut
bool 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 Code
int main()
{
 
    string s = "nolon";
 
    cout << solve(s);
 
    return 0;
}

Java

// Java program to solve the above problem
import java.util.Arrays;
 
class GFG
{
 
// Function to check if string is palindrome or not
static 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 cut
static 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 Code
public 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 not
def 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 cut
def 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 False
 
def 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 Code
if __name__ == '__main__':
    s = "nolon"
 
    print(solve(s))
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to solve the above problem
using System;
using System.Linq;
 
class GFG
{
 
// Function to check if string is palindrome or not
static 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 cut
static 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 Code
static 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 not
function 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 cut
function 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 Code
let s = "nolon";
document.write(solve(s));
 
// This code is contributed by rag2127
 
</script>

Output:

Time Complexity: O(N²)

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 even
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.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 odd
int 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 Code
int 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 2
 
def 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 problem
using 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 even
function 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 odd
function 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 Code
let s = "nolon";
document.write(solve(s));
 
// This code is contributed by avanitrachhadiya2155
</script>

Output:

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 zambiatek!