Remove characters that appear more than k times
Given a string of lowercase letters, reduce it by removing the characters which appear more than k times in the string.
Examples:
Input: str = "w3wiki" k = 2 Output: for Input: str = "w3wiki" k = 3 Output: gksforgks
Approach :
- Create a hash table of 26 indexes, where the 0th index represents ‘a’ and 1th index represents ‘b’ and so on. Initialize the hash table to zero.
- Iterate through the string and count increment the frequency of the str[i] character in the hash table.
- Now once again traverse through the string and append those characters in the new string whose frequency in the hash table is less than k and skip those which appear more than equal to k.
Time Complexity: O(N)
Below is the implementation of above approach:
C++
// C++ program to reduce the string by // removing the characters which // appears more than k times #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; void 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' ]++; // Next index in reduced string int index = 0; for ( int i = 0; i < n; ++i) { // Append the characters which // appears less than k times if (hash[arr[i] - 'a' ] < k) { arr[index++] = arr[i]; } } arr[index] = '\0' ; } int main() { char str[] = "w3wiki" ; int k = 2; removeChars(str, k); cout << str; return 0; } |
Java
// Java program to reduce the string by // removing the characters which // appears more than k times import java.util.*; class Solution { static final int MAX_CHAR = 26 ; static void removeChars( char arr[], int k) { // Hash table initialised to 0 int hash[]= new int [MAX_CHAR]; for ( int i = 0 ; i <MAX_CHAR; ++i) hash[i]= 0 ; // Increment the frequency of the character int n = (arr).length; for ( int i = 0 ; i < n; ++i) hash[arr[i] - 'a' ]++; // Next index in reduced string int index = 0 ; for ( int i = 0 ; i < n; ++i) { // Append the characters which // appears less than k times if (hash[arr[i] - 'a' ] < k) { arr[index++] = arr[i]; } } for ( int i = index; i < n; ++i) arr[i] = ' ' ; } public static void main(String args[]) { char str[] = "w3wiki" .toCharArray();; int k = 2 ; removeChars(str, k); System.out.println(String.valueOf( str)); } } //contributed by Arnab Kundu |
Python3
# Python 3 program to reduce the string by # removing the characters which # appears more than k times MAX_CHAR = 26 def removeChars(arr, k): # Hash table initialised to 0 hash = [ 0 for i in range (MAX_CHAR)] # Increment the frequency of the character n = len (arr) for i in range (n): hash [ ord (arr[i]) - ord ( 'a' )] + = 1 # Next index in reduced string index = 0 for i in range (n): # Append the characters which # appears less than k times if ( hash [ ord (arr[i]) - ord ( 'a' )] < k): arr[index] = arr[i] index + = 1 arr[index] = ' ' for i in range (index): print (arr[i], end = '') # Driver code if __name__ = = '__main__' : str = "w3wiki" str = list ( str ) k = 2 removeChars( str , k) # This code is contributed by # Shashank_Sharma |
C#
// C# program to reduce the string by // removing the characters which // appears more than k times using System; public class Solution{ static readonly int MAX_CHAR = 26; static void removeChars( char []arr, int k) { // Hash table initialised to 0 int []hash= new int [MAX_CHAR]; for ( int i = 0; i <MAX_CHAR; ++i) hash[i]=0; // Increment the frequency of the character int n = (arr).Length; for ( int i = 0; i < n; ++i) hash[arr[i] - 'a' ]++; // Next index in reduced string int index = 0; for ( int i = 0; i < n; ++i) { // Append the characters which // appears less than k times if (hash[arr[i] - 'a' ] < k) { arr[index++] = arr[i]; } } for ( int i = index; i < n; ++i) arr[i] = ' ' ; } public static void Main() { char []str = "w3wiki" .ToCharArray();; int k = 2; removeChars(str, k); Console.Write(String.Join( "" ,str)); } } // This code is contributed by PrinciRaj1992 |
PHP
<?php // PHP program to reduce the string by // removing the characters which // appears more than k times $MAX_CHAR = 26; function removeChars( $arr , $k ) { global $MAX_CHAR ; // Hash table initialised to 0 $hash = array_fill (0, $MAX_CHAR , NULL); // Increment the frequency of // the character $n = strlen ( $arr ); for ( $i = 0; $i < $n ; ++ $i ) $hash [ord( $arr [ $i ]) - ord( 'a' )]++; // Next index in reduced string $index = 0; for ( $i = 0; $i < $n ; ++ $i ) { // Append the characters which // appears less than k times if ( $hash [ord( $arr [ $i ]) - ord( 'a' )] < $k ) { $arr [ $index ++] = $arr [ $i ]; } } $arr [ $index ] = '' ; for ( $i = 0; $i < $index ; $i ++) echo $arr [ $i ]; } // Driver Code $str = "w3wiki" ; $k = 2; removeChars( $str , $k ); // This code is contributed by ita_c ?> |
Javascript
<script> // JavaScript program to reduce the string by // removing the characters which // appears less than k times let MAX_CHAR = 26; // Function to reduce the string by // removing the characters which // appears less than k times function removeChars(str,k) { // Hash table initialised to 0 let hash = new Array(MAX_CHAR); for (let i=0;i<hash.length;i++) { hash[i]=0; } // Increment the frequency of the character let n = str.length; for (let i = 0; i < n; ++i) { hash[str[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; } // create a new empty string let index = "" ; for (let i = 0; i < n; ++i) { // Append the characters which // appears more than equal to k times if (hash[str[i].charCodeAt(0) - 'a' .charCodeAt(0)] < k) { index += str[i]; } } return index; } // Driver Code let str = "w3wiki" ; let k = 2; document.write(removeChars(str, k)); // This code is contributed by rag2127 </script> |
Output
for
Complexity Analysis:
- Time Complexity: O(n), where n represents the size of the given array.
- Auxiliary Space: O(1), no extra space is required, so it is a constant.
Method #2:Using Built-in Python functions:
- We will scan the string and count the occurrence of all characters using built-in Counter() function.
- Now once again traverse through the string and append those characters in the new string whose frequency in the frequency dictionary is less than k and skip those which appear more than equal to k.
Note: This method is applicable for all types of characters.
Below is the implementation of the above approach:
C++
#include <iostream> #include <unordered_map> using namespace std; // Function to reduce the string by // removing the characters which // appears more than k times string removeChars(string str, int k) { // Using unordered_map to count frequencies unordered_map< char , int > freq; for ( int i = 0; i < str.length(); i++) { char c = str[i]; freq++; } // create a new empty string string res = "" ; for ( int i = 0; i < str.length(); i++) { char c = str[i]; // Append the characters which // appears less than equal to k times if (freq < k) { res += c; } } return res; } // Driver code int main() { string str = "w3wiki" ; int k = 2; cout << removeChars(str, k) << endl; return 0; } |
Java
import java.util.*; public class Main { // Function to reduce the string by // removing the characters which // appears more than k times public static String removeChars(String str, int k) { // Using HashMap to count frequencies Map<Character, Integer> freq = new HashMap<>(); for ( int i = 0 ; i < str.length(); i++) { char c = str.charAt(i); freq.put(c, freq.getOrDefault(c, 0 ) + 1 ); } // create a new empty string StringBuilder res = new StringBuilder(); for ( int i = 0 ; i < str.length(); i++) { char c = str.charAt(i); // Append the characters which // appears less than equal to k times if (freq.get(c) < k) { res.append(c); } } return res.toString(); } // Driver code public static void main(String[] args) { String str = "w3wiki" ; int k = 2 ; System.out.println(removeChars(str, k)); } } |
Python3
# Python 3 program to reduce the string # by removing the characters which # appears more than k times from collections import Counter # Function to reduce the string by # removing the characters which # appears more than k times def removeChars( str , k): # Using Counter function to # count frequencies freq = Counter( str ) # create a new empty string res = "" for i in range ( len ( str )): # Append the characters which # appears less than equal to k times if (freq[ str [i]] < k): res + = str [i] return res # Driver Code if __name__ = = "__main__" : str = "w3wiki" k = 2 print (removeChars( str , k)) # This code is contributed by vikkycirus |
C#
using System; using System.Collections.Generic; class Gfg { // Function to reduce the string by // removing the characters which // appears more than k times static string RemoveChars( string str, int k) { // Using Dictionary to count frequencies Dictionary< char , int > freq = new Dictionary< char , int >(); for ( int i = 0; i < str.Length; i++) { char c = str[i]; if (!freq.ContainsKey(c)) { freq.Add(c, 0); } freq++; } // create a new empty string string res = "" ; for ( int i = 0; i < str.Length; i++) { char c = str[i]; // Append the characters which // appears less than equal to k times if (freq < k) { res += c; } } return res; } // Driver code static void Main( string [] args) { string str = "w3wiki" ; int k = 2; Console.WriteLine(RemoveChars(str, k)); } } |
Javascript
// Function to reduce the string by // removing the characters which // appears more than k times function removeChars(str, k) { // Using object to count frequencies let freq = {}; for (let i = 0; i < str.length; i++) { freq[str[i]] = (freq[str[i]] || 0) + 1; } // create a new empty string let res = "" ; for (let i = 0; i < str.length; i++) { // Append the characters which // appears less than equal to k times if (freq[str[i]] < k) { res += str[i]; } } return res; } // Driver Code let str = "w3wiki" ; let k = 2; console.log(removeChars(str, k)); // This code is contributed by codebraxnzt |
Output
for
Complexity Analysis:
- Time Complexity: O(n), where n represents the size of the given array.
- Auxiliary Space: O(1), no extra space is required, so it is a constant.