Minimize the length of string by removing occurrence of only one character
Given a string str containing only lowercase alphabets, the task is to minimize the length of the string after performing the following operation:
- Delete all occurrences of any one character from this string.
Examples:
Input: str = “abccderccwq”
Output: 7
character ‘c’ will be deleted since it has maximum occurrence.Input: str = “dddded”
Output: 1
Explanation: character ‘d’ will be deleted
Approach:
- Maintain the frequency of each and every character in an array.
- Find the character with the maximum frequency.
- Finally, subtract the length of the original string with the frequency of that character to get the desired answer.
Implementation:
C++
// C++ program to minimize the length of string by // removing occurrence of only one character #include <bits/stdc++.h> using namespace std; // Function to find the minimum length int minimumLength(string s) { int maxOcc = 0, n = s.length(); int arr[26] = {0}; // Count the frequency of each alphabet for ( int i = 0; i < n; i++) arr[s[i] - 'a' ]++; // Find the alphabets with maximum frequency for ( int i = 0; i < 26; i++) if (arr[i] > maxOcc) maxOcc = arr[i]; // Subtract the frequency of character // from length of string return (n - maxOcc); } // Driver Code int main() { string str = "afddewqd" ; cout << minimumLength(str); return 0; } |
Java
// Java program to minimize the length of string // by removing occurrence of only one character import java.io.*; class GFG { // Function to find the minimum length static int minimumLength(String s) { int maxOcc = 0 , n = s.length(); int arr[] = new int [ 26 ]; // Count the frequency of each alphabet for ( int i = 0 ; i < n; i++) arr[s.charAt(i) - 'a' ]++; // Find the alphabets with maximum frequency for ( int i = 0 ; i < 26 ; i++) if (arr[i] > maxOcc) maxOcc = arr[i]; // Subtract the frequency of character // from length of string return (n - maxOcc); } // Driver Code public static void main (String[] args) { String str = "afddewqd" ; System.out.println( minimumLength(str)); } } //This code is contributed by chandan_jnu... |
Python 3
# Python 3 program to minimize the length of string # by removing occurrence of only one character # Function to find the minimum length def minimumLength(s) : maxOcc = 0 n = len (s) arr = [ 0 ] * 26 # Count the frequency of each alphabet for i in range (n) : arr[ ord (s[i]) - ord ( 'a' )] + = 1 # Find the alphabets with maximum frequency for i in range ( 26 ) : if arr[i] > maxOcc : maxOcc = arr[i] # Subtract the frequency of character # from length of string return n - maxOcc # Driver Code if __name__ = = "__main__" : str = "afddewqd" print (minimumLength( str )) # This code is contributed by ANKITRAI1 |
C#
// C# program to minimize the // length of string by removing // occurrence of only one character using System; class GFG { // Function to find the minimum length static int minimumLength(String s) { int maxOcc = 0, n = s.Length; int []arr = new int [26]; // Count the frequency of each alphabet for ( int i = 0; i < n; i++) arr[s[i] - 'a' ]++; // Find the alphabets with // maximum frequency for ( int i = 0; i < 26; i++) if (arr[i] > maxOcc) maxOcc = arr[i]; // Subtract the frequency of character // from length of string return (n - maxOcc); } // Driver Code public static void Main (String[] args) { String str = "afddewqd" ; Console.WriteLine( minimumLength(str)); } } // This code is contributed by // PrinciRaj1992 |
Javascript
<script> // Javascript program to minimize the length of string by // removing occurrence of only one character // Function to find the minimum length function minimumLength(s) { var maxOcc = 0, n = s.length; var arr = Array(26).fill(0); // Count the frequency of each alphabet for ( var i = 0; i < n; i++) arr[s[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; // Find the alphabets with maximum frequency for ( var i = 0; i < 26; i++) if (arr[i] > maxOcc) maxOcc = arr[i]; // Subtract the frequency of character // from length of string return (n - maxOcc); } // Driver Code var str = "afddewqd" ; document.write( minimumLength(str)); </script> |
Output
5
Time complexity: O(n) where n is the length of string
Auxiliary space: O(1) since constant space is being used
Contact Us