Minimum letters to be removed to make all occurrences of a given letter continuous
Given a string str and a character K, the task is to find the minimum number of elements that should be removed from this sequence so that all occurrences of the given character K become continuous.
Examples:
Input: str = “ababababa”, K = ‘a’
Output: 4
Explanation:
All the occurrences of the character ‘b’ should be removed in order to make the occurrences of ‘a’ continuous.Input: str = “kprkkoinkopt”, K = ‘k’
Output: 5
Approach: The idea is to find the number of characters other than K in between the first and last occurrence of the given character K. In order to do this, the following steps are followed:
- Find the first occurrence of the character K.
- Find the last occurrence of the character K.
- Iterate between the indices and find the number of characters present in between those indices other than K. This is the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum number of // deletions required to make the occurrences // of the given character K continuous int noOfDeletions(string str, char k) { int ans = 0, cnt = 0, pos = 0; // Find the first occurrence of the given letter while (pos < str.length() && str[pos] != k) { pos++; } int i = pos; // Iterate from the first occurrence // till the end of the sequence while (i < str.length()) { // Find the index from where the occurrence // of the character is not continuous while (i < str.length() && str[i] == k) { i = i + 1; } // Update the answer with the number of // elements between non-consecutive occurrences // of the given letter ans = ans + cnt; cnt = 0; while (i < str.length() && str[i] != k) { i = i + 1; // Update the count for all letters // which are not equal to the given letter cnt = cnt + 1; } } // Return the count return ans; } // Driver code int main() { string str1 = "ababababa" ; char k1 = 'a' ; // Calling the function cout << noOfDeletions(str1, k1) << endl; string str2 = "kprkkoinkopt" ; char k2 = 'k' ; // Calling the function cout << noOfDeletions(str2, k2) << endl; } |
Java
// Java implementation of the above approach import java.util.*; class GFG{ // Function to find the minimum number of // deletions required to make the occurrences // of the given character K continuous static int noOfDeletions(String str, char k) { int ans = 0 , cnt = 0 , pos = 0 ; // Find the first occurrence of the given letter while (pos < str.length() && str.charAt(pos) != k) { pos++; } int i = pos; // Iterate from the first occurrence // till the end of the sequence while (i < str.length()) { // Find the index from where the occurrence // of the character is not continuous while (i < str.length() && str.charAt(i) == k) { i = i + 1 ; } // Update the answer with the number of // elements between non-consecutive occurrences // of the given letter ans = ans + cnt; cnt = 0 ; while (i < str.length() && str.charAt(i) != k) { i = i + 1 ; // Update the count for all letters // which are not equal to the given letter cnt = cnt + 1 ; } } // Return the count return ans; } // Driver code public static void main(String[] args) { String str1 = "ababababa" ; char k1 = 'a' ; // Calling the function System.out.print(noOfDeletions(str1, k1) + "\n" ); String str2 = "kprkkoinkopt" ; char k2 = 'k' ; // Calling the function System.out.print(noOfDeletions(str2, k2) + "\n" ); } } // This code is contributed by Princi Singh |
Python3
# Python3 implementation of the above approach # Function to find the minimum number of # deletions required to make the occurrences # of the given character K continuous def noOfDeletions(string, k) : ans = 0 ; cnt = 0 ; pos = 0 ; # Find the first occurrence of the given letter while (pos < len (string) and string[pos] ! = k) : pos + = 1 ; i = pos; # Iterate from the first occurrence # till the end of the sequence while (i < len (string)) : # Find the index from where the occurrence # of the character is not continuous while (i < len (string) and string[i] = = k) : i = i + 1 ; # Update the answer with the number of # elements between non-consecutive occurrences # of the given letter ans = ans + cnt; cnt = 0 ; while (i < len (string) and string[i] ! = k) : i = i + 1 ; # Update the count for all letters # which are not equal to the given letter cnt = cnt + 1 ; # Return the count return ans; # Driver code if __name__ = = "__main__" : str1 = "ababababa" ; k1 = 'a' ; # Calling the function print (noOfDeletions(str1, k1)); str2 = "kprkkoinkopt" ; k2 = 'k' ; # Calling the function print (noOfDeletions(str2, k2)); # This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the above approach // Function to find the minimum number of // deletions required to make the occurrences // of the given character K continuous function noOfDeletions(str, k) { var ans = 0, cnt = 0, pos = 0; // Find the first occurrence of the given letter while (pos < str.length && str[pos] != k) { pos++; } var i = pos; // Iterate from the first occurrence // till the end of the sequence while (i < str.length) { // Find the index from where the occurrence // of the character is not continuous while (i < str.length && str[i] == k) { i = i + 1; } // Update the answer with the number of // elements between non-consecutive occurrences // of the given letter ans = ans + cnt; cnt = 0; while (i < str.length && str[i] != k) { i = i + 1; // Update the count for all letters // which are not equal to the given letter cnt = cnt + 1; } } // Return the count return ans; } // Driver code var str1 = "ababababa" ; var k1 = 'a' ; // Calling the function document.write( noOfDeletions(str1, k1) + "<br>" ); var str2 = "kprkkoinkopt" ; var k2 = 'k' ; // Calling the function document.write( noOfDeletions(str2, k2)); // This code is contributed by rrrtnx </script> |
C#
// C# implementation of the above approach using System; class GFG{ // Function to find the minimum number of // deletions required to make the occurrences // of the given character K continuous static int noOfDeletions(String str, char k) { int ans = 0, cnt = 0, pos = 0; // Find the first occurrence of the given letter while (pos < str.Length && str[pos] != k) { pos++; } int i = pos; // Iterate from the first occurrence // till the end of the sequence while (i < str.Length) { // Find the index from where the occurrence // of the character is not continuous while (i < str.Length && str[i] == k) { i = i + 1; } // Update the answer with the number of // elements between non-consecutive occurrences // of the given letter ans = ans + cnt; cnt = 0; while (i < str.Length && str[i] != k) { i = i + 1; // Update the count for all letters // which are not equal to the given letter cnt = cnt + 1; } } // Return the count return ans; } // Driver code public static void Main(String[] args) { String str1 = "ababababa" ; char k1 = 'a' ; // Calling the function Console.Write(noOfDeletions(str1, k1) + "\n" ); String str2 = "kprkkoinkopt" ; char k2 = 'k' ; // Calling the function Console.Write(noOfDeletions(str2, k2) + "\n" ); } } // This code is contributed by Rajput-Ji |
4 5
Time Complexity: O(N) since one traversal of the string is required to complete all operations hence the overall time required by the algorithm is linear
Auxiliary Space: O(1) since no extra array is used the space taken by the algorithm is linear.
Another Approach:
Initialize a counter variable to zero, which will keep track of the number of letters removed.
Initialize two pointers, left and right, both pointing to the beginning of the string.
Move the right pointer to the first occurrence of the given letter in the string.
While the right pointer is not at the end of the string:
a. Move the left pointer to the next character after the last occurrence of the given letter in the current continuous sequence of the letter.
b. If there is no next occurrence of the given letter in the string, break the loop.
c. Calculate the number of letters between the current left and right pointers (excluding the first occurrence of the given letter).
d. If this number is greater than the current maximum number of letters between two occurrences of the given letter, update the maximum.
e. Move the right pointer to the next occurrence of the given letter in the string.
Subtract the maximum number of letters between two occurrences of the given letter from the total length of the string to get the minimum number of letters to be removed.
C
#include <stdio.h> #include <string.h> int min_letters_to_remove( char * str, char letter) { int len = strlen (str); int left = 0, right = 0; int max_letters = 0, count = 0; // Find the first occurrence of the letter while (right < len && str[right] != letter) { right++; } // Traverse the string and find the maximum number of // letters between two occurrences of the letter while (right < len) { // Move the left pointer to the next character after // the last occurrence of the letter while (left < right && str[left] != letter) { left++; } // If there is no next occurrence of the letter, // break the loop if (left == right) { break ; } // Calculate the number of letters between the left // and right pointers count = right - left - 1; // Update the maximum number of letters between two // occurrences of the letter if (count > max_letters) { max_letters = count; } // Move the right pointer to the next occurrence of // the letter right++; } // Return the minimum number of letters to be removed return len - max_letters - 1; } int main() { char str[] = "aabbccdd" ; char letter = 'b' ; int min_removed = min_letters_to_remove(str, letter); printf ( "Minimum letters to be removed: %d\n" , min_removed); return 0; } |
C++14
#include <cstring> #include <iostream> using namespace std; int min_letters_to_remove( char * str, char letter) { int len = strlen (str); int left = 0, right = 0; int max_letters = 0, count = 0; // Find the first occurrence of the letter while (right < len && str[right] != letter) { right++; } // Traverse the string and find the maximum number of // letters between two occurrences of the letter while (right < len) { // Move the left pointer to the next character after // the last occurrence of the letter while (left < right && str[left] != letter) { left++; } // If there is no next occurrence of the letter, // break the loop if (left == right) { break ; } // Calculate the number of letters between the left // and right pointers count = right - left - 1; // Update the maximum number of letters between two // occurrences of the letter if (count > max_letters) { max_letters = count; } // Move the right pointer to the next occurrence of // the letter right++; } // Return the minimum number of letters to be removed return len - max_letters - 1; } int main() { char str[] = "aabbccdd" ; char letter = 'b' ; int min_removed = min_letters_to_remove(str, letter); cout << "Minimum letters to be removed: " << min_removed << endl; return 0; } |
Java
/*package whatever //do not write package name here */ import java.util.*; public class Main { public static int minLettersToRemove( char [] str, char letter) { int len = str.length; int left = 0 , right = 0 ; int maxLetters = 0 , count = 0 ; // Find the first occurrence of the letter while (right < len && str[right] != letter) { right++; } // Traverse the string and find the maximum number // of // letters between two occurrences of the letter while (right < len) { // Move the left pointer to the next character // after // the last occurrence of the letter while (left < right && str[left] != letter) { left++; } // If there is no next occurrence of the letter, // break the loop if (left == right) { break ; } // Calculate the number of letters between the // left // and right pointers count = right - left - 1 ; // Update the maximum number of letters between // two // occurrences of the letter if (count > maxLetters) { maxLetters = count; } // Move the right pointer to the next occurrence // of // the letter right++; } // Return the minimum number of letters to be // removed return len - maxLetters - 1 ; } public static void main(String[] args) { char [] str = { 'a' , 'a' , 'b' , 'b' , 'c' , 'c' , 'd' , 'd' }; char letter = 'b' ; int minRemoved = minLettersToRemove(str, letter); System.out.println( "Minimum letters to be removed: " + minRemoved); } } |
Python3
def min_letters_to_remove(string, letter): length = len (string) left = 0 right = 0 max_letters = 0 count = 0 # Find the first occurrence of the letter while right < length and string[right] ! = letter: right + = 1 # Traverse the string and find the maximum number of # letters between two occurrences of the letter while right < length: # Move the left pointer to the next character after # the last occurrence of the letter while left < right and string[left] ! = letter: left + = 1 # If there is no next occurrence of the letter, # break the loop if left = = right: break # Calculate the number of letters between the left # and right pointers count = right - left - 1 # Update the maximum number of letters between two # occurrences of the letter if count > max_letters: max_letters = count # Move the right pointer to the next occurrence of # the letter right + = 1 # Return the minimum number of letters to be removed return length - max_letters - 1 if __name__ = = "__main__" : string = "aabbccdd" letter = 'b' min_removed = min_letters_to_remove(string, letter) print (f "Minimum letters to be removed: {min_removed}" ) |
Javascript
function min_letters_to_remove(str, letter) { const len = str.length; let left = 0, right = 0, max_letters = 0, count = 0; // Find the first occurrence of the letter while (right < len && str[right] !== letter) { right++; } // Traverse the string and find the maximum number of letters // between two occurrences of the letter while (right < len) { // Move the left pointer to the next character after // the last occurrence of the letter while (left < right && str[left] !== letter) { left++; } // If there is no next occurrence of the letter, // break the loop if (left === right) { break ; } // Calculate the number of letters between the left // and right pointers count = right - left - 1; // Update the maximum number of letters between two // occurrences of the letter if (count > max_letters) { max_letters = count; } // Move the right pointer to the next occurrence of // the letter right++; } // Return the minimum number of letters to be removed return len - max_letters - 1; } const str = "aabbccdd" ; const letter = "b" ; const min_removed = min_letters_to_remove(str, letter); console.log( "Minimum letters to be removed:" , min_removed); |
C#
using System; class Program { static int MinLettersToRemove( string str, char letter) { int len = str.Length; int left = 0, right = 0; int maxLetters = 0, count = 0; // Find the first occurrence of the letter while (right < len && str[right] != letter) { right++; } // Traverse the string and find the maximum number // of letters between two occurrences of the letter while (right < len) { // Move the left pointer to the next character // after the last occurrence of the letter while (left < right && str[left] != letter) { left++; } // If there is no next occurrence of the letter, // break the loop if (left == right) { break ; } // Calculate the number of letters between the // left and right pointers count = right - left - 1; // Update the maximum number of letters between // two occurrences of the letter if (count > maxLetters) { maxLetters = count; } // Move the right pointer to the next occurrence // of the letter right++; } // Return the minimum number of letters to be // removed return len - maxLetters - 1; } static void Main( string [] args) { string str = "aabbccdd" ; char letter = 'b' ; int minRemoved = MinLettersToRemove(str, letter); Console.WriteLine( "Minimum letters to be removed: {0}" , minRemoved); } } |
Minimum letters to be removed: 7
time complexity of O(n), where n is the size of the string
space complexity of O(1)