Minimum replacements such that no palindromic substring of length exceeding 1 is present in the given string
Given a string str consisting of lowercase characters, the task is to modify the string such that it does not contain any palindromic substring of length exceeding 1 by minimum replacement of characters.
Examples:
Input: str = �”
Output: 4
String can be modified to “bacbacb” by replacing 4 characters.Input: str = “w3wiki”
Output: 2
Approach 1:
To solve the problem, the idea is that, if there exists a palindrome of length larger than 3, then there exists a palindrome of length 2 or 3. Therefore, greedily remove all palindromes of length 2 or 3. Follow the steps below to solve the problem:
- Initialize a variable, say change, to store the required number of replacements.
- Iterate over the characters of the given string and perform the following steps:
- If the character at the current index is the same as the character at the next index, then increment change by 1.
- Otherwise, check if the character at the previous index is the same as the character at the next index, i.e. there is a palindromic substring of length 3. Therefore, increment change by 1.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count the changes required such // that no palindromic substring of length // exceeding 1 is present in the string int maxChange(string str) { // Base Case if (str.size() <= 1) { return 0; } // Stores the count int minChanges = 0; // Iterate over the string for ( int i = 0; i < str.size() - 1; i++) { // Palindromic Substring of Length 2 if (str[i] == str[i + 1]) { // Replace the next character str[i + 1] = 'N' ; // Increment changes minChanges += 1; } // Palindromic Substring of Length 3 else if (i > 0 && str[i - 1] == str[i + 1]) { // Replace the next character str[i + 1] = 'N' ; // Increment changes minChanges += 1; } } return minChanges; } // Driver Code int main() { string str = "bbbbbbb" ; cout << maxChange(str); return 0; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to count the changes required such // that no palindromic subString of length // exceeding 1 is present in the String static int maxChange( char []str) { // Base Case if (str.length <= 1 ) { return 0 ; } // Stores the count int minChanges = 0 ; // Iterate over the String for ( int i = 0 ; i < str.length - 1 ; i++) { // Palindromic SubString of Length 2 if (str[i] == str[i + 1 ]) { // Replace the next character str[i + 1 ] = 'N' ; // Increment changes minChanges += 1 ; } // Palindromic SubString of Length 3 else if (i > 0 && str[i - 1 ] == str[i + 1 ]) { // Replace the next character str[i + 1 ] = 'N' ; // Increment changes minChanges += 1 ; } } return minChanges; } // Driver Code public static void main(String[] args) { String str = "bbbbbbb" ; System.out.print(maxChange(str.toCharArray())); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 Program to implement # the above approach # Function to count the changes required such # that no palindromic subof length # exceeding 1 is present in the string def maxChange( str ): str = [i for i in str ] if ( len ( str ) < = 1 ): return 0 # Stores the count minChanges = 0 # Iterate over the string for i in range ( len ( str ) - 1 ): # Palindromic Subof Length 2 if ( str [i] = = str [i + 1 ]): # Replace the next character str [i + 1 ] = 'N' # Increment changes minChanges + = 1 # Palindromic Subof Length 3 elif (i > 0 and str [i - 1 ] = = str [i + 1 ]): # Replace the next character str [i + 1 ] = 'N' # Increment changes minChanges + = 1 return minChanges # Driver Code if __name__ = = '__main__' : str = "bbbbbbb" print (maxChange( str )) # This code is contributed by mohit kumar 29. |
C#
// C# Program to implement // the above approach using System; public class GFG { // Function to count the changes required such // that no palindromic subString of length // exceeding 1 is present in the String static int maxChange( char []str) { // Base Case if (str.Length <= 1) { return 0; } // Stores the count int minChanges = 0; // Iterate over the String for ( int i = 0; i < str.Length - 1; i++) { // Palindromic SubString of Length 2 if (str[i] == str[i + 1]) { // Replace the next character str[i + 1] = 'N' ; // Increment changes minChanges += 1; } // Palindromic SubString of Length 3 else if (i > 0 && str[i - 1] == str[i + 1]) { // Replace the next character str[i + 1] = 'N' ; // Increment changes minChanges += 1; } } return minChanges; } // Driver Code public static void Main(String[] args) { String str = "bbbbbbb" ; Console.Write(maxChange(str.ToCharArray())); } } // This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count the changes required such // that no palindromic subString of length // exceeding 1 is present in the String function maxChange(str) { // Base Case if (str.length <= 1) { return 0; } // Stores the count var minChanges = 0; // Iterate over the String for ( var i = 0; i < str.length - 1; i++) { // Palindromic SubString of Length 2 if (str[i] === str[i + 1]) { // Replace the next character str[i + 1] = "N" ; // Increment changes minChanges += 1; } // Palindromic SubString of Length 3 else if (i > 0 && str[i - 1] === str[i + 1]) { // Replace the next character str[i + 1] = "N" ; // Increment changes minChanges += 1; } } return minChanges; } // Driver Code var str = "bbbbbbb" ; document.write(maxChange(str.split( "" ))); </script> |
4
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(1), as we are not using any extra space.
Approach 2:
- Initialize variables n to store the size of the string and changes to keep track of the number of changes made.
- Iterate over the string using a for loop from index 0 to n – 1.
- Now check for palindromic substrings of length 2 or 3 by comparing the current character str[i] with the next character str[i + 1] and the character before str[i – 1] with the character after str[i + 1].
- If a palindromic substring is found, replace the next character str[i + 1] with a different character (e.g., ‘N’) to break the palindrome, and increment the changes variable to keep track of the number of changes made.
- Return the value.
Below is the Code of the above approach:
C++
#include <algorithm> #include <iostream> using namespace std; int maxChange(string str) { int n = str.size(); int changes = 0; // Iterate over the string for ( int i = 0; i < n - 1; i++) { // Check for palindromic substrings of length 2 or 3 if (str[i] == str[i + 1] || (i > 0 && str[i - 1] == str[i + 1])) { // Replace the next character with a different // character str[i + 1] = 'N' ; // Increment changes changes++; } } return changes; } // Nikunj Sonigara int main() { string str = "bbbbbbb" ; cout << maxChange(str) << endl; return 0; } |
Java
import java.util.*; // Class public class GFG { // Main driver method public static int maxChange(String str) { int n = str.length(); int changes = 0 ; // Iterate over the string for ( int i = 0 ; i < n - 1 ; i++) { // Check for palindromic substrings of length 2 // or 3 if (str.charAt(i) == str.charAt(i + 1 ) || (i > 0 && str.charAt(i - 1 ) == str.charAt(i + 1 ))) { // Replace the next character with a // different character StringBuilder sb = new StringBuilder(str); sb.setCharAt(i + 1 , 'N' ); str = sb.toString(); // Increment changes changes++; } } return changes; } // Nikunj Sonigara public static void main(String[] args) { String str = "bbbbbbb" ; System.out.println(maxChange(str)); } } |
Python3
def max_change(s): n = len (s) changes = 0 # Iterate over the string for i in range (n - 1 ): # Check for palindromic substrings of length 2 or 3 if s[i] = = s[i + 1 ] or (i > 0 and s[i - 1 ] = = s[i + 1 ]): # Replace the next character with a different character s = s[:i + 1 ] + 'N' + s[i + 2 :] # Increment changes changes + = 1 return changes # Nikunj Sonigara # Test the function str = "bbbbbbb" print (max_change( str )) |
C#
using System; class GFG { static int MaxChange( string str) { int n = str.Length; int changes = 0; // Iterate over the string for ( int i = 0; i < n - 1; i++) { // Check for palindromic substrings of length 2 or 3 if (str[i] == str[i + 1] || (i > 0 && str[i - 1] == str[i + 1])) { // Replace the next character with a different character str = str.Substring(0, i + 1) + 'N' + str.Substring(i + 2); // Increment changes changes++; } } return changes; } static void Main() { string str = "bbbbbbb" ; Console.WriteLine(MaxChange(str)); } } |
Javascript
function maxChange(str) { let n = str.length; let changes = 0; // Iterate over the string for (let i = 0; i < n - 1; i++) { // Check for palindromic substrings of length 2 or 3 if (str[i] === str[i + 1] || (i > 0 && str[i - 1] === str[i + 1])) { // Replace the next character with a different character str = str.substring(0, i + 1) + 'N' + str.substring(i + 2); // Increment changes changes++; } } return changes; } // Nikunj Sonigara function main() { let str = "bbbbbbb" ; console.log(maxChange(str)); } // Call the main function main(); |
4
Time Complexity: O(N), where N is the length of the input string.
Auxiliary Space: O(1)
Contact Us