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 timesstring 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 codeint 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 timesimport java.util.*;class GFG{ static int MAX_CHAR = 26; // Function to reduce the String by// removing the characters which// appears exactly k timesstatic 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 codepublic 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 timesMAX_CHAR = 26# Function to reduce the string by# removing the characters which# appears exactly k timesdef 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 codeif __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 timesusing System;class GFG{ static int MAX_CHAR = 26; // Function to reduce the String by// removing the characters which// appears exactly k timesstatic 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 codepublic 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 timeslet MAX_CHAR = 26; // Function to reduce the String by// removing the characters which// appears exactly k timesfunction 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> |
Output:
eeforee
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N)
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!
