Minimum operation require to make first and last character same
Given a string S. You are allowed two types of operations:
- Remove a character from the front of the string.
- Remove a character from the end of the string.
The task is to find the minimum operations required to make the first and last character of the S same. In case, it is not possible, print “-1”.
Examples:
Input : S = "bacdefghipalop" Output : 4 Remove 'b' from the front and remove 'p', 'o', 'l' from the end of the string S. Input : S = "pqr" Output : -1
Approaches:
Recursive: Call a recursive function passing four arguments string, starting index, ending index and count of the number of eliminations still now.
Below is the implementation of the above approach:
C++
// CPP program to minimum operation require // to make first and last character same #include <bits/stdc++.h> using namespace std; const int MAX = INT_MAX; // Recursive function call int minOperation(string &s, int i, int j, int count) { if ((i>=s.size() && j<0) || (i == j)) return MAX; if (s[i] == s[j]) return count; // Decrement ending index only if (i >=s.size()) return minOperation(s,i,j-1,count+1); // Increment starting index only else if (j<0) return minOperation(s,i+1,j,count+1); // Increment starting index and decrement index else return min(minOperation(s,i,j-1,count+1),minOperation(s,i+1,j,count+1)); } // Driver code int main() { string s = "bacdefghipalop" ; // Function call int ans = minOperation(s,0,s.size()-1,0); if (ans == MAX) cout<<-1; else cout<<ans; return 0; } |
Java
// Java program to minimum operation require // to make first and last character same import java.util.*; class GFG { static final int MAX = Integer.MAX_VALUE; // Recursive function call static int minOperation(String s, int i, int j, int count) { if ((i >= s.length() && j < 0 ) || (i == j)) return MAX; if (s.charAt(i) == s.charAt(j)) return count; // Decrement ending index only if (i >= s.length()) return minOperation(s, i, j - 1 , count + 1 ); // Increment starting index only else if (j < 0 ) return minOperation(s, i + 1 , j, count + 1 ); // Increment starting index and decrement index else return Math.min(minOperation(s, i, j - 1 , count + 1 ), minOperation(s, i + 1 , j, count + 1 )); } // Driver Code public static void main(String[] args) { String s = "bacdefghipalop" ; // Function call int ans = minOperation(s, 0 , s.length() - 1 , 0 ); if (ans == MAX) System.out.println(- 1 ); else System.out.println(ans); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to minimum operation require # to make first and last character same import sys MAX = sys.maxsize # Recursive function call def minOperation(s, i, j, count): if ((i > = len (s) and j < 0 ) or (i = = j)): return MAX if (s[i] = = s[j]): return count # Decrement ending index only if (i > = len (s)): return minOperation(s, i, j - 1 , count + 1 ) # Increment starting index only elif (j < 0 ): return minOperation(s, i + 1 , j, count + 1 ) # Increment starting index # and decrement index else : return min (minOperation(s, i, j - 1 , count + 1 ), minOperation(s, i + 1 , j, count + 1 )) # Driver code if __name__ = = '__main__' : s = "bacdefghipalop" # Function call ans = minOperation(s, 0 , len (s) - 1 , 0 ) if (ans = = MAX ): print ( - 1 ) else : print (ans) # This code is contributed by mohit kumar 29 |
C#
// C# program to minimum operation require // to make first and last character same using System; class GFG { static int MAX = Int32.MaxValue; // Recursive function call static int minOperation( string s, int i, int j, int count) { if ((i >= s.Length && j < 0) || (i == j)) return MAX; if (s[i] == s[j]) return count; // Decrement ending index only if (i >= s.Length) return minOperation(s, i, j - 1, count + 1); // Increment starting index only else if (j < 0) return minOperation(s, i + 1, j, count + 1); // Increment starting index and decrement index else return Math.Min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1)); } // Driver Code public static void Main() { string s = "bacdefghipalop" ; // Function call int ans = minOperation(s, 0, s.Length - 1, 0); if (ans == MAX) Console.Write(-1); else Console.Write(ans); } } // This code is contributed by susmitakundugoaldanga |
Javascript
<script> // Javascript program to minimum operation require // to make first and last character same var MAX = 1000000000; // Recursive function call function minOperation( s,i,j,count) { if ((i>=s.length && j<0) || (i == j)) return MAX; if (s[i] == s[j]) return count; // Decrement ending index only if (i >=s.length) return minOperation(s,i,j-1,count+1); // Increment starting index only else if (j<0) return minOperation(s,i+1,j,count+1); // Increment starting index and decrement index else return Math.min(minOperation(s,i,j-1,count+1), minOperation(s,i+1,j,count+1)); } // Driver code var s = "bacdefghipalop" ; // Function call var ans = minOperation(s,0,s.length-1,0); if (ans == MAX) document.write( -1); else document.write( ans); </script> |
4
Dynamic Programming: The idea is to prevent making further recursive calls for count>= Min once we found the Min during every recursive call. It saves a lot of time and is almost comparable to the tabulation method in terms of time complexity.
Implementation:
CPP
// CPP program to find minimum operation require // to make first and last character same #include <bits/stdc++.h> using namespace std; const int MAX = INT_MAX; // To store the visited strings map <string, int > m; int Min = INT_MAX; // Function to find minimum operation require // to make first and last character same int minOperation(string &s, int i, int j, int count) { // Base conditions if ((i>=s.size() && j<0) || (i == j)) return MAX; // If answer found if (s[i] == s[j] || (count >= Min)) return count; string str = to_string(i) + "|" +to_string(j); // If string is already visited if (m.find(str) == m.end()) { // Decrement ending index only if (i >=s.size()) m[str]= minOperation(s,i,j-1,count+1); // Increment starting index only else if (j<0) m[str]= minOperation(s,i+1,j,count+1); // Increment starting index and decrement index else m[str]= min(minOperation(s,i,j-1,count+1),minOperation(s,i+1,j,count+1)); } // Store the minimum value if (m[str] < Min) Min = m[str]; return m[str]; } // Driver code int main() { string s = "bacdefghipalop" ; // Function call int ans = minOperation(s,0,s.size()-1,0); if (ans == MAX) cout<<-1; else cout<<ans; } |
Java
// Java program to find minimum operation require // to make first and last character same import java.io.*; import java.util.*; class GFG { static int MAX = Integer.MAX_VALUE; static HashMap<String, Integer> m = new HashMap<>(); static int Min = Integer.MAX_VALUE; // Function to find minimum operation require // to make first and last character same static int minOperation(String s, int i, int j, int count) { // Base conditions if ((i >= s.length() && j < 0 )|| (i == j)) { return MAX; } // If answer found if (s.charAt(i) == s.charAt(j) || (count >= Min)) { return count; } String str = String.valueOf(i) + "|" + String.valueOf(j); // If string is already visited if (!m.containsKey(str)) { // Decrement ending index only if (i >= s.length()) { m.put(str,minOperation(s, i, j - 1 , count + 1 )); } // Increment starting index only else if (j < 0 ) { m.put(str,minOperation(s, i + 1 , j, count + 1 )); } // Increment starting index and decrement index else { m.put(str,Math.min(minOperation(s, i, j - 1 , count + 1 ), minOperation(s, i + 1 , j, count + 1 ))); } } // Store the minimum value if (m.get(str) < Min) { Min = m.get(str); } return m.get(str); } // Driver code public static void main (String[] args) { String s = "bacdefghipalop" ; // Function call int ans=minOperation(s, 0 , s.length() - 1 , 0 ); if (ans == MAX) { System.out.println(- 1 ); } else { System.out.println(ans); } } } // This code is contributed by rag2127 |
Python3
# Python program to find minimum operation require # to make first and last character same import sys MAX = sys.maxsize # To store the visited strings m = {} Min = sys.maxsize # Function to find minimum operation require # to make first and last character same def minOperation(s, i, j, count): global Min , MAX # Base conditions if ((i > = len (s) and j < 0 ) or (i = = j)): return MAX # If answer found if (s[i] = = s[j] or count > = Min ): return count Str = str (i) + "|" + str (j) # If string is already visited if Str not in m: # Decrement ending index only if (i > = len (s)): m[ Str ] = minOperation(s, i, j - 1 , count + 1 ) # Increment starting index only elif (j < 0 ): m[ Str ] = minOperation(s, i + 1 , j, count + 1 ) # Increment starting index and decrement index else : m[ Str ] = min (minOperation(s, i, j - 1 , count + 1 ), minOperation(s, i + 1 , j, count + 1 )) # Store the minimum value if (m[ Str ] < Min ): Min = m[ Str ] return m[ Str ] # Driver code s = "bacdefghipalop" # Function call ans = minOperation(s, 0 , len (s) - 1 , 0 ) if (ans = = MAX ): print ( - 1 ) else : print (ans) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program to find minimum operation require // to make first and last character same using System; using System.Collections.Generic; class GFG { static int MAX = Int32.MaxValue; static Dictionary< string , int > m = new Dictionary< string , int >(); static int Min = Int32.MaxValue; // Function to find minimum operation require // to make first and last character same static int minOperation( string s, int i, int j, int count) { // Base conditions if ((i >= s.Length && j < 0)|| (i == j)) { return MAX; } // If answer found if (s[i] == s[j] || (count >= Min)) { return count; } string str = i.ToString() + "|" + j.ToString(); // If string is already visited if (!m.ContainsKey(str)) { // Decrement ending index only if (i >= s.Length) { m[str] = minOperation(s, i, j - 1, count + 1); } // Increment starting index only else if (j < 0) { m[str] = minOperation(s, i + 1, j, count + 1); } // Increment starting index and decrement index else { m[str] = Math.Min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1)); } } // Store the minimum value if (m[str] < Min) { Min = m[str]; } return m[str]; } // Driver code static void Main() { string s = "bacdefghipalop" ; // Function call int ans=minOperation(s, 0, s.Length - 1, 0); if (ans == MAX) { Console.WriteLine(-1); } else { Console.WriteLine(ans); } } } // This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program to find minimum operation require // to make first and last character same let MAX = Number.MAX_VALUE; let m = new Map(); let Min = Number.MAX_VALUE; // Function to find minimum operation require // to make first and last character same function minOperation(s, i, j, count) { // Base conditions if ((i >= s.length && j < 0)|| (i == j)) { return MAX; } // If answer found if (s[i] == s[j] || (count >= Min)) { return count; } let str = (i).toString() + "|" + (j).toString(); // If string is already visited if (!m.has(str)) { // Decrement ending index only if (i >= s.length) { m.set(str,minOperation(s, i, j - 1, count + 1)); } // Increment starting index only else if (j < 0) { m.set(str,minOperation(s, i + 1, j, count + 1)); } // Increment starting index and decrement index else { m.set(str,Math.min(minOperation(s, i, j - 1, count + 1), minOperation(s, i + 1, j, count + 1))); } } // Store the minimum value if (m.get(str) < Min) { Min = m.get(str); } return m.get(str); } // Driver code let s = "bacdefghipalop" ; // Function call let ans=minOperation(s, 0, s.length - 1, 0); if (ans == MAX) { document.write(-1); } else { document.write(ans); } // This code is contributed by unknown2108 </script> |
4
Dynamic programming with Tabulation:
The idea is to find the first and last occurrences of each character in the string. The total amount of operations needed will be simply “number of operations needed to remove the first occurrence” plus “number of operations needed to remove the last occurrence”. So, do this for each character in the string and the answer will be a minimum of such operations performed on each character.
For example, S = “zabcdefghaabbbb”, calculate the operations required to have character ‘a’ at both the front and the end, meaning to say the string “a….a”. For the minimum number of operations, we will form the string “abcdefghaa” i.e we will remove one character ‘z’ from front and 4 characters ‘bbbb’ from back. Hence total 5 operations will be required.
So, apply the above algorithm for each character and hence we can then find the minimum of those operations.
Implementation:
C++
// C++ program to find minimum operation // require to make first and last character same #include <bits/stdc++.h> using namespace std; #define MAX 256 // Return the minimum operation require // to make string first and last character same. int minimumOperation(string s) { int n = s.length(); // Store indexes of first occurrences of characters. vector< int > first_occ(MAX, -1); // Initialize result int res = INT_MAX; // Traverse through all characters for ( int i=0; i<n; i++) { // Find first occurrence char x = s[i]; if (first_occ[x] == -1) first_occ[x] = i; // Update result for subsequent occurrences else { int last_occ = (n-i-1); res = min(res, first_occ[x] + last_occ); } } return res; } // Driven Program int main() { string s = "bacdefghipalop" ; cout << minimumOperation(s) << endl; return 0; } |
Java
// Java program to find minimum // operation require to make // first and last character same import java.util.*; import java.lang.*; import java.io.*; class GFG{ static final int MAX= 256 ; // Return the minimum operation requires to // make string first and last character same. static int minimumOperation(String s) { int n = s.length(); // Store indexes of first occurrences of characters. Vector<Integer> first_occ= new Vector<Integer>(); //Initialize all the elements to -1 for ( int i= 0 ;i<MAX;i++) first_occ.add(i,- 1 ); // Initialize result int res = Integer.MAX_VALUE; // Traverse through all characters for ( int i= 0 ; i<n; i++) { // Find first occurrence int x = ( int )s.charAt(i); if (first_occ.elementAt(x) == - 1 ) first_occ.set(x,i); // Update result for subsequent occurrences else { int last_occ = (n-i- 1 ); res = Math.min(res, first_occ.get(x) + last_occ); } } return res; } // Driven Program public static void main(String args[]) { String s = "bacdefghipalop" ; System.out.println(minimumOperation(s)); } } |
Python3
# Python3 program to find minimum operation # require to make first and last character same MAX = 256 # Return the minimum operation require to # make string first and last character same. def minimumOperation(s): n = len (s) # Store indexes of first # occurrences of characters. first_occ = [ - 1 ] * MAX # Initialize result res = float ( 'inf' ) # Traverse through all characters for i in range ( 0 , n): # Find first occurrence x = s[i] if first_occ[ ord (x)] = = - 1 : first_occ[ ord (x)] = i # Update result for subsequent occurrences else : last_occ = n - i - 1 res = min (res, first_occ[ ord (x)] + last_occ) return res # Driver Code if __name__ = = "__main__" : s = "bacdefghipalop" print (minimumOperation(s)) # This code is contributed by Rituraj Jain |
C#
// C# program to find minimum // operation require to make // first and last character same using System; using System.Collections.Generic; class GFG { static int MAX = 256; // Return the minimum operation requires to // make string first and last character same. static int minimumOperation(String s) { int n = s.Length; // Store indexes of first occurrences of characters. List< int > first_occ = new List< int >(); //Initialize all the elements to -1 for ( int i = 0; i < MAX; i++) first_occ.Insert(i,-1); // Initialize result int res = int .MaxValue; // Traverse through all characters for ( int i = 0; i < n; i++) { // Find first occurrence int x = ( int )s[i]; if (first_occ[x] == -1) first_occ.Insert(x,i); // Update result for subsequent occurrences else { int last_occ = (n - i - 1); res = Math.Min(res, first_occ[x] + last_occ); } } return res; } // Driver code public static void Main(String []args) { String s = "bacdefghipalop" ; Console.WriteLine(minimumOperation(s)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to find minimum operation // require to make first and last character same const MAX = 256 // Return the minimum operation require // to make string first and last character same. function minimumOperation(s) { let n = s.length; // Store indexes of first occurrences of characters. let first_occ = new Array(MAX).fill(-1); // Initialize result let res = Number.MAX_VALUE; // Traverse through all characters for (let i=0; i<n; i++) { // Find first occurrence let x = s.charCodeAt(i); if (first_occ[x] == -1) first_occ[x] = i; // Update result for subsequent occurrences else { let last_occ = (n-i-1); res = Math.min(res, first_occ[x] + last_occ); } } return res; } // Driven Program let s = "bacdefghipalop" ; document.write(minimumOperation(s)); // This code is contributed by shinjanpatra </script> |
4
Time Complexity: O(n)
Contact Us