Given a string str, the task is to make the string start and end at the same character with the minimum number of given operations. In a single operation, any character of the string can be removed. Note that the length of the resultant string must be greater than 1 and it is not possible then print -1.
Examples:
Input: str = “neveropen”
Output: 3
Remove the first and the last two characters
and the string becomes “eeksforgee”Input: str = “abcda”
Output: 0
Approach: If the string needs to start and end at a character say ch then an optimal way is to remove all the characters before the first occurrence of ch and all the characters after the last occurrence of ch. Find the number of characters that need to be removed for every possible value of ch starting from ‘a’ to ‘z’ and choose the one with the minimum number of delete operations.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 26;// Function to return the minimum// operations requiredint minOperation(string str, int len){ // To store the first and the last // occurrence of all the characters int first[MAX], last[MAX]; // Set the first and the last occurrence // of all the characters to -1 for (int i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (int i = 0; i < len; i++) { int index = (str[i] - 'a'); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the minimum operations int minOp = -1; for (int i = 0; i < MAX; i++) { // If the frequency of the current // character in the string // is less than 2 if (first[i] == -1 || first[i] == last[i]) continue; // Count of characters to be // removed so that the string // starts and ends at the // current character int cnt = len - (last[i] - first[i] + 1); if (minOp == -1 || cnt < minOp) minOp = cnt; } return minOp;}// Driver codeint main(){ string str = "abcda"; int len = str.length(); cout << minOperation(str, len); return 0;} |
Java
// Java implementation of the approach class GFG{ final static int MAX = 26; // Function to return the minimum // operations required static int minOperation(String str, int len) { // To store the first and the last // occurrence of all the characters int first[] = new int[MAX]; int last[] = new int[MAX]; // Set the first and the last occurrence // of all the characters to -1 for (int i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (int i = 0; i < len; i++) { int index = (str.charAt(i) - 'a'); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the minimum operations int minOp = -1; for (int i = 0; i < MAX; i++) { // If the frequency of the current // character in the string // is less than 2 if (first[i] == -1 || first[i] == last[i]) continue; // Count of characters to be // removed so that the string // starts and ends at the // current character int cnt = len - (last[i] - first[i] + 1); if (minOp == -1 || cnt < minOp) minOp = cnt; } return minOp; } // Driver code public static void main (String[] args) { String str = "abcda"; int len = str.length(); System.out.println(minOperation(str, len)); } }// This code is contributed by AnkitRai01 |
Python3
# Python implementation of the approachMAX = 26;# Function to return the minimum# operations requireddef minOperation(str, len): # To store the first and the last # occurrence of all the characters first, last = [0] * MAX, [0] * MAX; # Set the first and the last occurrence # of all the characters to -1 for i in range(MAX): first[i] = -1; last[i] = -1; # Update the occurrences of the characters for i in range(len): index = (ord(str[i]) - ord('a')); # Only set the first occurrence if # it hasn't already been set if (first[index] == -1): first[index] = i; last[index] = i; # To store the minimum operations minOp = -1; for i in range(MAX): # If the frequency of the current # character in the string # is less than 2 if (first[i] == -1 or first[i] == last[i]): continue; # Count of characters to be # removed so that the string # starts and ends at the # current character cnt = len - (last[i] - first[i] + 1); if (minOp == -1 or cnt < minOp): minOp = cnt; return minOp;# Driver codestr = "abcda";len = len(str);print( minOperation(str, len));# This code is contributed by 29AjayKumar |
C#
// C# implementation of the approach using System; class GFG{ readonly static int MAX = 26; // Function to return the minimum // operations required static int minOperation(String str, int len) { // To store the first and the last // occurrence of all the characters int []first = new int[MAX]; int []last = new int[MAX]; // Set the first and the last occurrence // of all the characters to -1 for (int i = 0; i < MAX; i++) { first[i] = -1; last[i] = -1; } // Update the occurrences of the characters for (int i = 0; i < len; i++) { int index = (str[i] - 'a'); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the minimum operations int minOp = -1; for (int i = 0; i < MAX; i++) { // If the frequency of the current // character in the string // is less than 2 if (first[i] == -1 || first[i] == last[i]) continue; // Count of characters to be // removed so that the string // starts and ends at the // current character int cnt = len - (last[i] - first[i] + 1); if (minOp == -1 || cnt < minOp) minOp = cnt; } return minOp; } // Driver code public static void Main (String[] args) { String str = "abcda"; int len = str.Length; Console.WriteLine(minOperation(str, len)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar MAX = 26;// Function to return the minimum// operations requiredfunction minOperation(str, len){ // To store the first and the last // occurrence of all the characters var first = Array(MAX).fill(-1); var last = Array(MAX).fill(-1); // Update the occurrences of the characters for (var i = 0; i < len; i++) { var index = (str[i].charCodeAt(0) - 'a'.charCodeAt(0)); // Only set the first occurrence if // it hasn't already been set if (first[index] == -1) first[index] = i; last[index] = i; } // To store the minimum operations var minOp = -1; for (var i = 0; i < MAX; i++) { // If the frequency of the current // character in the string // is less than 2 if (first[i] == -1 || first[i] == last[i]) continue; // Count of characters to be // removed so that the string // starts and ends at the // current character var cnt = len - (last[i] - first[i] + 1); if (minOp == -1 || cnt < minOp) minOp = cnt; } return minOp;}// Driver codevar str = "abcda";var len = str.length;document.write( minOperation(str, len));</script> |
Output:
0
Time Complexity: O(len), where len is length of string.
Auxiliary Space : O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
