Given a string of lowercase letters str of length N, the task is to reduce it by removing the characters which appear exactly K times in the string.
Examples:
Input: str = “neveropen”, K = 2
Output: eeforeeInput: str = “neveropen”, K = 4
Output: gksforgks
Approach:
- Create a hash table of size 26, where 0th index represents ‘a’ and 1st index represent ‘b’ and so on.
- Initialize the hash table to zero.
- Iterate through the string and increment the frequency of each character(s[i]) in the hash table
- Now, once again traverse through the string and append the characters, with frequency K, in the new string.
Below is the implementation of the above approach:
C++
// C++ program to remove characters from // a String that appears exactly K times #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; // Function to reduce the string by // removing the characters which // appears exactly k times string removeChars( char arr[], int k) { // Hash table initialised to 0 int hash[MAX_CHAR] = { 0 }; // Increment the frequency // of the character int n = strlen (arr); for ( int i = 0; i < n; ++i) hash[arr[i] - 'a' ]++; // To store answer string ans = "" ; // Next index in reduced string int index = 0; for ( int i = 0; i < n; ++i) { // Append the characters which // appears exactly k times if (hash[arr[i] - 'a' ] != k) { ans += arr[i]; } } return ans; } // Driver code int main() { char str[] = "neveropen" ; int k = 2; // Function call cout << removeChars(str, k); return 0; } |
Java
// Java program to remove characters from // a String that appears exactly K times import java.util.*; class GFG{ static int MAX_CHAR = 26 ; // Function to reduce the String by // removing the characters which // appears exactly k times static String removeChars( char arr[], int k) { // Hash table initialised to 0 int []hash = new int [MAX_CHAR]; // Increment the frequency // of the character int n = arr.length; for ( int i = 0 ; i < n; ++i) hash[arr[i] - 'a' ]++; // To store answer String ans = "" ; for ( int i = 0 ; i < n; ++i) { // Append the characters which // appears exactly k times if (hash[arr[i] - 'a' ] != k) { ans += arr[i]; } } return ans; } // Driver code public static void main(String[] args) { char str[] = "neveropen" .toCharArray(); int k = 2 ; // Function call System.out.print(removeChars(str, k)); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program to remove characters from # a String that appears exactly K times MAX_CHAR = 26 # Function to reduce the string by # removing the characters which # appears exactly k times def removeChars(arr, k): # Hash table initialised to 0 hash = [ 0 ] * MAX_CHAR # Increment the frequency # of the character n = len (arr) for i in range ( n): hash [ ord (arr[i]) - ord ( 'a' )] + = 1 # To store answer ans = "" # Next index in reduced string index = 0 for i in range (n): # Append the characters which # appears exactly k times if ( hash [ ord (arr[i]) - ord ( 'a' )] ! = k): ans + = arr[i] return ans # Driver code if __name__ = = "__main__" : str = "neveropen" k = 2 # Function call print (removeChars( str , k)) # This code is contributed by chitranayal |
C#
// C# program to remove characters from // a String that appears exactly K times using System; class GFG{ static int MAX_CHAR = 26; // Function to reduce the String by // removing the characters which // appears exactly k times static String removeChars( char []arr, int k) { // Hash table initialised to 0 int []hash = new int [MAX_CHAR]; // Increment the frequency // of the character int n = arr.Length; for ( int i = 0; i < n; ++i) hash[arr[i] - 'a' ]++; // To store answer String ans = "" ; for ( int i = 0; i < n; ++i) { // Append the characters which // appears exactly k times if (hash[arr[i] - 'a' ] != k) { ans += arr[i]; } } return ans; } // Driver code public static void Main(String[] args) { char []str = "neveropen" .ToCharArray(); int k = 2; // Function call Console.Write(removeChars(str, k)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to remove characters from // a String that appears exactly K times let MAX_CHAR = 26; // Function to reduce the String by // removing the characters which // appears exactly k times function removeChars(arr, k) { // Hash table initialised to 0 let hash = Array.from({length: MAX_CHAR}, (_, i) => 0); // Increment the frequency // of the character let n = arr.length; for (let i = 0; i < n; ++i) hash[arr[i].charCodeAt() - 'a' .charCodeAt()]++; // To store answer let ans = "" ; for (let i = 0; i < n; ++i) { // Append the characters which // appears exactly k times if (hash[arr[i].charCodeAt() - 'a' .charCodeAt()] != k) { ans += arr[i]; } } return ans; } // Driver code let str = "neveropen" .split( '' ); let k = 2; // Function call document.write(removeChars(str, k)); </script> |
eeforee
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!