Given a string str, the task is to find the minimum length of substring required to rotate that generates a palindromic substring from the given string.
Examples:
Input: str = “abcbd”
Output: 0
Explanation: No palindromic substring can be generated. There is no repeated character in the string.
Input: str = “abcdeba”
Output: 3
Explanation: Rotate substring “deb” to convert the given string to abcbeda with a palindromic substring “bcb”.
Approach:
- If no character repeats in the string, then no palindromic substring can be generated.
- For every repeating character, check if the index of its previous occurrence is within one or two indices from the current index. If so, then a palindromic substring already exists.
- Otherwise, calculate the length of (current index – index of the previous occurrence – 1).
- Return the minimum of all such lengths as the answer
Below is the implementation of the above approach:
C++
// C++ Program to find the minimum // length of substring whose rotation // generates a palindromic substring #include <bits/stdc++.h> using namespace std; // Function to return the // minimum length of substring int count_min_length(string s) { // Store the index of // previous occurrence // of the character int hash[26]; // Variable to store // the maximum length // of substring int ans = INT_MAX; for ( int i = 0; i < 26; i++) hash[i] = -1; for ( int i = 0; i < s.size(); i++) { // If the current character // hasn't appeared yet if (hash[s[i] - 'a' ] == -1) hash[s[i] - 'a' ] = i; else { // If the character has occurred // within one or two previous // index, a palindromic substring // already exists if (hash[s[i] - 'a' ] == i - 1 || hash[s[i] - 'a' ] == i - 2) return 0; // Update the maximum ans = min(ans, i - hash[s[i] - 'a' ] - 1); // Replace the previous // index of the character by // the current index hash[s[i] - 'a' ] = i; } } // If character appeared // at least twice if (ans == INT_MAX) return -1; return ans; } // Driver Code int main() { string str = "abcdeba" ; cout << count_min_length(str); } |
Java
// Java Program to find the minimum // length of substring whose rotation // generates a palindromic substring import java.util.*; import java.lang.*; class GFG{ // Function to return the // minimum length of substring static int count_min_length(String s) { // Store the index of // previous occurrence // of the character int [] hash = new int [ 26 ]; // Variable to store // the maximum length // of substring int ans = Integer.MAX_VALUE; for ( int i = 0 ; i < 26 ; i++) hash[i] = - 1 ; for ( int i = 0 ; i < s.length(); i++) { // If the current character // hasn't appeared yet if (hash[s.charAt(i) - 'a' ] == - 1 ) hash[s.charAt(i) - 'a' ] = i; else { // If the character has occurred // within one or two previous // index, a palindromic substring // already exists if (hash[s.charAt(i) - 'a' ] == i - 1 || hash[s.charAt(i) - 'a' ] == i - 2 ) return 0 ; // Update the maximum ans = Math.min(ans, i - hash[s.charAt(i) - 'a' ] - 1 ); // Replace the previous // index of the character by // the current index hash[s.charAt(i) - 'a' ] = i; } } // If character appeared // at least twice if (ans == Integer.MAX_VALUE) return - 1 ; return ans; } // Driver code public static void main(String[] args) { String str = "abcdeba" ; System.out.println(count_min_length(str)); } } // This code is contributed by offbeat |
Python3
# Python3 program to find the minimum # length of substring whose rotation # generates a palindromic substring import sys INT_MAX = sys.maxsize; # Function to return the # minimum length of substring def count_min_length(s): # Store the index of # previous occurrence # of the character hash = [ 0 ] * 26 ; # Variable to store # the maximum length # of substring ans = sys.maxsize; for i in range ( 26 ): hash [i] = - 1 ; for i in range ( len (s)): # If the current character # hasn't appeared yet if ( hash [ ord (s[i]) - ord ( 'a' )] = = - 1 ): hash [ ord (s[i]) - ord ( 'a' )] = i; else : # If the character has occurred # within one or two previous # index, a palindromic substring # already exists if ( hash [ ord (s[i]) - ord ( 'a' )] = = i - 1 or hash [ ord (s[i]) - ord ( 'a' )] = = i - 2 ) : return 0 ; # Update the maximum ans = min (ans, i - hash [ ord (s[i]) - ord ( 'a' )] - 1 ); # Replace the previous # index of the character by # the current index hash [ ord (s[i]) - ord ( 'a' )] = i; # If character appeared # at least twice if (ans = = INT_MAX): return - 1 ; return ans; # Driver Code if __name__ = = "__main__" : string = "abcdeba" ; print (count_min_length(string)); # This code is contributed by AnkitRai01 |
C#
// C# Program to find the minimum // length of substring whose rotation // generates a palindromic substring using System; class GFG{ // Function to return the // minimum length of substring static int count_min_length( string s) { // Store the index of // previous occurrence // of the character int [] hash = new int [26]; // Variable to store // the maximum length // of substring int ans = int .MaxValue; for ( int i = 0; i < 26; i++) hash[i] = -1; for ( int i = 0; i < s.Length; i++) { // If the current character // hasn't appeared yet if (hash[s[i] - 'a' ] == -1) hash[s[i] - 'a' ] = i; else { // If the character has occurred // within one or two previous // index, a palindromic substring // already exists if (hash[s[i] - 'a' ] == i - 1 || hash[s[i] - 'a' ] == i - 2) return 0; // Update the maximum ans = Math.Min(ans, i - hash[s[i] - 'a' ] - 1); // Replace the previous // index of the character by // the current index hash[s[i] - 'a' ] = i; } } // If character appeared // at least twice if (ans == int .MaxValue) return -1; return ans; } // Driver code public static void Main( string [] args) { string str = "abcdeba" ; Console.WriteLine(count_min_length(str)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript Program to find the minimum // length of substring whose rotation // generates a palindromic substring // Function to return the // minimum length of substring function count_min_length(s) { // Store the index of // previous occurrence // of the character var hash = new Array(26).fill(0); // Variable to store // the maximum length // of substring var ans = 2147483648; for ( var i = 0; i < 26; i++) hash[i] = -1; for ( var i = 0; i < s.length; i++) { // If the current character // hasn't appeared yet if (hash[s[i].charCodeAt(0) - "a" .charCodeAt(0)] == -1) hash[s[i].charCodeAt(0) - "a" .charCodeAt(0)] = i; else { // If the character has occurred // within one or two previous // index, a palindromic substring // already exists if ( hash[s[i].charCodeAt(0) - "a" .charCodeAt(0)] == i - 1 || hash[s[i].charCodeAt(0) - "a" .charCodeAt(0)] == i - 2 ) return 0; // Update the maximum ans = Math.min( ans, i - hash[s[i].charCodeAt(0) - "a" .charCodeAt(0)] - 1 ); // Replace the previous // index of the character by // the current index hash[s[i].charCodeAt(0) - "a" .charCodeAt(0)] = i; } } // If character appeared // at least twice if (ans === 2147483648) return -1; return ans; } // Driver code var str = "abcdeba" ; document.write(count_min_length(str)); </script> |
3
Time Complexity: O(N), as we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(26), as we are using extra space for hash.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!