Given numeric string str, the task is to find the minimum operations needed to make the string palindrome. An operation is defined as:
- Select one character and remove any of its occurrences.
- For all the operations, the number of unique characters chosen must be less than 2
Examples:
Input: str = “11221”
Output: 1
Explanation: Select ‘1’ and remove anyone character out of the first two characters of the given string. After the operation, the string becomes “1221” which is a palindrome.Input: str = “1123211”
Output: 0
Explanation: The given string is already a palindrome.Input: str = “1332”
Output: -1
Explanation: The string can’t be made palindrome after selecting a single character and removing the occurrences of the selected character only.
Approach: This problem can be solved with the help of the two-pointer approach.
Follow the steps below to solve the problem:
- Initialize a variable answer as n that stores our final answer (n is the length of the string).
- Iterate over ‘0’ to ‘9’ and let’s call it currentCharacter.
- Initialize toBeRemoved as 0. It stores the minimum number of characters to be removed of currentCharacter type from the string to make it a palindrome.
- Initialize i and j as 0 and n – 1 respectively.
- Initialize a possible as true. It helps us to determine whether it is possible to make the string palindrome by removing the occurrences of the character c only.
- Now run a nested while loop till i is less than j.
- Case 1: str[i] is equal to str[j], It means that we are not required to remove any character at the present step so we can increment i and decrement j.
- Case 2: str[i] is not equal to str[j] but str[i] is equal to currentCharacter. Increment i = i + 1 and toBeRemoved = toBeRemoved + 1 as we are removing this character.
- Case 3: str[i] is not equal to str[j] but str[j] is equal to currentCharacter. Increment j = j – 1 and toBeRemoved = toBeRemoved + 1 as we are removing this character
- Case 4: str[i] is not equal to str[j]. It means that we can’t make our string palindrome by removing the currentCharacter.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum operationsvoid solve(string str){ // Length of the string int n = str.length(); // answer variable for final answer // initializing it with INF int answer = n; // Iterating over characters // from '0' to '9' (string // consist of those characters only) for (char currentCharacter = '0'; currentCharacter <= '9'; currentCharacter++) { // i and j variables to check corresponding // characters from the start and the end int i = 0, j = n - 1; // toBeRemoved store the character of type // currentCharacter to be removed // to make the string palindrome int toBeRemoved = 0; bool possible = true; while (i < j) { // If corresponding currentCharacters are // already same if (str[i] == str[j]) { i++, j--; } // If corresponding currentCharacters are // not same and str[i] is equal to // currentCharacter // remove it and check for str[i + 1] and // str[j] in the next iteration else if (str[i] != str[j] && str[i] == currentCharacter) { toBeRemoved++; i++; } // If corresponding currentCharacters are // not same and str[j] is equal to // currentCharacter // remove it and check for str[j - 1] and // str[i] in the next iteration else if (str[i] != str[j] && str[j] == currentCharacter) { toBeRemoved++; j--; } // Character of currentCharacter type // can't be removed // to make the str palindrome. // Hence, we mark possible to false // break out of the loop else { possible = false; break; } } // If it is possible to remove // some occurrences of currentCharacters // we will update our answer if (possible) // Take the minimum value out // of answer and toBeRemoved answer = min(answer, toBeRemoved); } // Print the final answer if (answer == n) cout << "-1"; else cout << answer;}// Driver Codeint main(){ // Given string string str = "11221"; solve(str);} |
Java
// Java code for the above approachimport java.io.*;class GFG{ // Function to find the minimum operations static void solve(String str) { // Length of the string int n = str.length(); // answer variable for final answer // initializing it with INF int answer = n; // Iterating over characters // from '0' to '9' (string // consist of those characters only) for (char currentCharacter = '0'; currentCharacter <= '9'; currentCharacter++) { // i and j variables to check corresponding // characters from the start and the end int i = 0, j = n - 1; // toBeRemoved store the character of type // currentCharacter to be removed // to make the string palindrome int toBeRemoved = 0; boolean possible = true; while (i < j) { // If corresponding currentCharacters are // already same if (str.charAt(i) == str.charAt(j)) { i++; j--; } // If corresponding currentCharacters are // not same and str[i] is equal to // currentCharacter // remove it and check for str[i + 1] and // str[j] in the next iteration else if (str.charAt(i) != str.charAt(j) && str.charAt(i) == currentCharacter) { toBeRemoved++; i++; } // If corresponding currentCharacters are // not same and str[j] is equal to // currentCharacter // remove it and check for str[j - 1] and // str[i] in the next iteration else if (str.charAt(i) != str.charAt(j) && str.charAt(j) == currentCharacter) { toBeRemoved++; j--; } // Character of currentCharacter type // can't be removed // to make the str palindrome. // Hence, we mark possible to false // break out of the loop else { possible = false; break; } } // If it is possible to remove // some occurrences of currentCharacters // we will update our answer if (possible) // Take the minimum value out // of answer and toBeRemoved answer = Math.min(answer, toBeRemoved); } // Print the final answer if (answer == n) System.out.println("-1"); else System.out.println(answer); } // Driver Code public static void main (String[] args) { // Given string String str = "11221"; solve(str); }}// This code is contributed by lokeshpotta20. |
Python3
# Python program for the above approach# Function to find the minimum operationsdef solve(str): # Length of the string n = len(str) # answer variable for final answer # initializing it with INF answer = n; currentCharacter = '0' # Iterating over characters # from '0' to '9' (string # consist of those characters only) while(currentCharacter <= '9'): # i and j variables to check corresponding # characters from the start and the end i = 0 j = n - 1 # toBeRemoved store the character of type # currentCharacter to be removed # to make the string palindrome toBeRemoved = 0 possible = True while (i < j): # If corresponding currentCharacters are # already same if (str[i] == str[j]): i += 1 j -= 1 # If corresponding currentCharacters are # not same and str[i] is equal to # currentCharacter # remove it and check for str[i + 1] and # str[j] in the next iteration elif (str[i] != str[j] and str[i] == currentCharacter): toBeRemoved += 1 i += 1 # If corresponding currentCharacters are # not same and str[j] is equal to # currentCharacter # remove it and check for str[j - 1] and # str[i] in the next iteration elif (str[i] != str[j] and str[j] == currentCharacter): toBeRemoved += 1 j -= 1 # Character of currentCharacter type # can't be removed # to make the str palindrome. # Hence, we mark possible to false # break out of the loop else: possible = False; break; currentCharacter = f"{int(currentCharacter) + 1}" # If it is possible to remove # some occurrences of currentCharacters # we will update our answer if (possible): # Take the minimum value out # of answer and toBeRemoved answer = min(answer, toBeRemoved); # Print the final answer if (answer == n): print("-1"); else: print(answer);# Driver Code# Given stringstr = "11221";solve(str);# This code is contributed by Saurabh Jaiswal |
C#
// C# program for above approachusing System;class GFG{// Function to find the minimum operationsstatic void solve(string str){ // Length of the string int n = str.Length; // answer variable for final answer // initializing it with INF int answer = n; // Iterating over characters // from '0' to '9' (string // consist of those characters only) for (char currentCharacter = '0'; currentCharacter <= '9'; currentCharacter++) { // i and j variables to check corresponding // characters from the start and the end int i = 0, j = n - 1; // toBeRemoved store the character of type // currentCharacter to be removed // to make the string palindrome int toBeRemoved = 0; bool possible = true; while (i < j) { // If corresponding currentCharacters are // already same if (str[i] == str[j]) { i++; j--; } // If corresponding currentCharacters are // not same and str[i] is equal to // currentCharacter // remove it and check for str[i + 1] and // str[j] in the next iteration else if (str[i] != str[j] && str[i] == currentCharacter) { toBeRemoved++; i++; } // If corresponding currentCharacters are // not same and str[j] is equal to // currentCharacter // remove it and check for str[j - 1] and // str[i] in the next iteration else if (str[i] != str[j] && str[j] == currentCharacter) { toBeRemoved++; j--; } // Character of currentCharacter type // can't be removed // to make the str palindrome. // Hence, we mark possible to false // break out of the loop else { possible = false; break; } } // If it is possible to remove // some occurrences of currentCharacters // we will update our answer if (possible) // Take the minimum value out // of answer and toBeRemoved answer = Math.Min(answer, toBeRemoved); } // Print the final answer if (answer == n) Console.Write("-1"); else Console.Write(answer);}// Driver Codepublic static void Main(){ // Given string string str = "11221"; solve(str);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum operationsfunction solve(str){ // Length of the string let n = str.length; // answer variable for final answer // initializing it with INF let answer = n; // Iterating over characters // from '0' to '9' (string // consist of those characters only) for (let currentCharacter = '0'; currentCharacter <= '9'; currentCharacter++) { // i and j variables to check corresponding // characters from the start and the end let i = 0, j = n - 1; // toBeRemoved store the character of type // currentCharacter to be removed // to make the string palindrome let toBeRemoved = 0; let possible = true; while (i < j) { // If corresponding currentCharacters are // already same if (str[i] == str[j]) { i++; j--; } // If corresponding currentCharacters are // not same and str[i] is equal to // currentCharacter // remove it and check for str[i + 1] and // str[j] in the next iteration else if (str[i] != str[j] && str[i] == currentCharacter) { toBeRemoved++; i++; } // If corresponding currentCharacters are // not same and str[j] is equal to // currentCharacter // remove it and check for str[j - 1] and // str[i] in the next iteration else if (str[i] != str[j] && str[j] == currentCharacter) { toBeRemoved++; j--; } // Character of currentCharacter type // can't be removed // to make the str palindrome. // Hence, we mark possible to false // break out of the loop else { possible = false; break; } } // If it is possible to remove // some occurrences of currentCharacters // we will update our answer if (possible) // Take the minimum value out // of answer and toBeRemoved answer = Math.min(answer, toBeRemoved); } // Print the final answer if (answer == n) document.write("-1"); else document.write(answer);}// Driver Code// Given stringlet str = "11221";solve(str);// This code is contributed by Samim Hossain Mondal.</script> |
Output
1
Time complexity: O(10 * n) = O(n) where n is the length of the string str.
Auxiliary Space: O(1)
