Given a string str and an integer K, the task is to reduce the string by applying the following operation any number of times until it is no longer possible:
Choose a group of K consecutive identical characters and remove them from the string.
Finally, print the reduced string.
Examples:
Input: K = 2, str = “neveropen”
Output: gksforgks
Explanation: After removal of both occurrences of the substring “ee”, the string reduces to “gksforgks”.Input: K = 3, str = “qddxxxd”
Output: q
Explanation:
Removal of “xxx” modifies the string to “qddd”.
Again, removal of “ddd”modifies the string to “q”.
Approach: This problem can be solved using the Stack data structure. Follow the steps below to solve the problem:
- Initialize a stack of pair<char, int>, to store characters and their respective consecutive frequencies.
- Iterate over the characters of the string.
- If the current character is different from the character present currently at the top of the stack, then set its frequency to 1.
- Otherwise, if the current character is the same as the character at the top of the stack, then increase its frequency by 1.
- If the frequency of the character at the top of the stack is K, pop that out of the stack.
- Finally, print the characters which are remaining in the stack as the resultant string.
Below is the implementation of the above approach:
C++
// CPP program for the above approach#include <bits/stdc++.h>#include <iostream>using namespace std;// Basic Approach is to create a Stack that store the// Character and its continuous repetition number This is// done using pair<char,int> Further we check at each// iteration, whether the character matches the top of stack// if it does then check for number of repetitions// else add to top of stack with count 1class Solution {public: string remove_k_char(int k, string s) { // Base Case // If k=1 then all characters // can be removed at each // instance if (k == 1) return ""; // initialize string string output = ""; // create a stack using pair<> for storing each // character and corresponding // repetition stack<pair<char, int> > stk; // iterate through the string for (int i = 0; i < s.length(); i++) { // if stack is empty then simply add the // character with count 1 else check if // character is same as top of stack if (stk.empty() == true) { stk.push(make_pair(s[i], 1)); } else { // if character at top of stack is same as // current character increase the number of // repetitions in the top of stack by 1 if (s[i] == (stk.top()).first) { pair<char, int> P = stk.top(); stk.pop(); P.second++; if (P.second == k) continue; else stk.push(P); } else { // if character at top of stack is not // same as current character push the // character along with count 1 into the // top of stack stk.push(make_pair(s[i], 1)); } } } // Iterate through the stack // Use string(int,char) in order to replicate the // character multiple times and convert into string // then add in front of output string while (!stk.empty()) { if (stk.top().second > 1) { // if Frequency of current character greater // than 1(let m),then append that character // m times in output string int count = stk.top().second; while (count--) output += stk.top().first; } else { output += stk.top().first; } stk.pop(); } reverse(output.begin(), output.end()); return output; }};// Driver Codeint main(){ string s = "neveropen"; int k = 2; Solution obj; cout << obj.remove_k_char(k, s) << "\n"; return 0;}// This Code has been contributed by shubhamm050402 |
C
#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct { char ch; int freq;} Pair;Pair createPair(char ch, int freq){ Pair p; p.ch = ch; p.freq = freq; return p;}void push(Pair* stack, int* top, char ch, int freq){ Pair p = createPair(ch, freq); stack[++(*top)] = p;}Pair pop(Pair* stack, int* top) { return stack[(*top)--]; }char* remove_k_char(int k, char* s){ if (k == 1) return ""; Pair stack[strlen(s)]; int top = -1; for (int i = 0; i < strlen(s); i++) { if (top == -1 || stack[top].ch != s[i]) push(stack, &top, s[i], 1); else { stack[top].freq++; if (stack[top].freq == k) pop(stack, &top); } } int resultLength = top + 1; char* result = (char*)malloc((resultLength + 1) * sizeof(char)); for (int i = 0; i < resultLength; i++) result[i] = stack[i].ch; result[resultLength] = '\0'; return result;}int main(){ char s[] = "neveropen"; int k = 2; char* result = remove_k_char(k, s); printf("%s\n", result); free(result); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function to find the reduced string public static String reduced_String(int k, String s) { // Base Case if (k == 1) { // all elements remove,send empty string return ""; } // Creating a stack of type Pair Stack<Pair> st = new Stack<Pair>(); // Length of the string S int l = s.length(); int ctr = 0; // iterate through the string for (int i = 0; i < l; i++) { // if stack is empty then simply add the // character with count 1 else check if // character is same as top of stack if (st.size() == 0) { st.push(new Pair(s.charAt(i), 1)); continue; } // if character at top of stack is same as // current character increase the number of // repetitions in the top of stack by 1 if (st.peek().c == s.charAt(i)) { Pair p = st.peek(); st.pop(); p.ctr += 1; if (p.ctr == k) { continue; } else { st.push(p); } } else { st.push(new Pair(s.charAt(i), 1)); } } // iterate through the stack // append characters in String StringBuilder output = new StringBuilder(); while (st.size() > 0) { char c = st.peek().c; int cnt = st.peek().ctr; // If frequency of a character is cnt, then // append that character to cnt times in String while (cnt-- > 0) output.append(String.valueOf(c)); st.pop(); } output.reverse(); return output.toString(); } // Driver code public static void main(String[] args) { int k = 2; String st = "neveropen"; String ans = reduced_String(k, st); System.out.println(ans); } // Pair Class static class Pair { char c; int ctr; Pair(char c, int ctr) { this.c = c; this.ctr = ctr; } }}// This Code has been contributed by shubhamm050402 |
Python3
# Python3 implementation of the approach# Pair class to store character and freqclass Pair: def __init__(self,c ,ctr): self.c= c self.ctr = ctrclass Solution: # Function to find the reduced string def reduced_String(self , k , s): #Base Case if (k == 1): return "" # Creating a stack of type Pair st = [] # iterate through given string for i in range(len(s)): # if stack is empty then simply add the # character with count 1 else check if # character is same as top of stack if (len(st) == 0): st.append((Pair(s[i] , 1))) continue # if character at top of stack is same as # current character increase the number of # repetitions in the top of stack by 1 if (st[-1].c == s[i]): pair = st.pop() pair.ctr +=1 if (pair.ctr == k): continue else: st.append(pair) else: # if character at top of stack is not # same as current character push the # character along with count 1 into the # top of stack st.append((Pair(s[i] , 1))) # Iterate through the stack # Use string(int,char) in order to replicate the # character multiple times and convert into string # then add in front of output string ans = "" while(len(st) > 0): c = st[-1].c cnt = st[-1].ctr while(cnt >0): ans = c + ans cnt -= 1 st.pop() return (ans)# Driver codeif __name__ == "__main__": k = 2 s = "neveropen" obj = Solution() print(obj.reduced_String(k,s)) # This code is contributed by chantya17. |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic;public class GFG { // Function to find the reduced string public static String reduced_String(int k, String s) { // Base Case if (k == 1) { return ""; } // Creating a stack of type Pair Stack<Pair> st = new Stack<Pair>(); // Length of the string S int l = s.Length; // iterate through the string for (int i = 0; i < l; i++) { // if stack is empty then simply add the // character with count 1 else check if // character is same as top of stack if (st.Count == 0) { st.Push(new Pair(s[i], 1)); continue; } // if character at top of stack is same as // current character increase the number of // repetitions in the top of stack by 1 if (st.Peek().c == s[i]) { Pair p = st.Peek(); st.Pop(); p.ctr += 1; if (p.ctr == k) { continue; } else { st.Push(p); } } else { // if character at top of stack is not // same as current character push the // character along with count 1 into the // top of stack st.Push(new Pair(s[i], 1)); } } // iterate through the stack // Use string(int,char) in order to replicate the // character multiple times and convert into string // then add in front of output string String ans = ""; while (st.Count > 0) { char c = st.Peek().c; int cnt = st.Peek().ctr; while (cnt-- > 0) ans = c + ans; st.Pop(); } return ans; } // Driver code public static void Main(String[] args) { int k = 2; String st = "neveropen"; String ans = reduced_String(k, st); Console.Write(ans); } public class Pair { public char c; public int ctr; public Pair(char c, int ctr) { this.c = c; this.ctr = ctr; } }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachclass Pair{ constructor(c,ctr) { this.c = c; this.ctr = ctr; }}// Function to find the reduced stringfunction reduced_String(k,s){ // Base Case if (k == 1) { let ans = ""; return ans; } // Creating a stack of type Pair let st = []; // Length of the string S let l = s.length; let ctr = 0; // iterate through the string for (let i = 0; i < l; i++) { // if stack is empty then simply add the // character with count 1 else check if // character is same as top of stack if (st.length == 0) { st.push(new Pair(s[i], 1)); continue; } // if character at top of stack is same as // current character increase the number of // repetitions in the top of stack by 1 if (st[st.length-1].c == s[i]) { let p = st[st.length-1]; st.pop(); p.ctr += 1; if (p.ctr == k) { continue; } else { st.push(p); } } else { // if character at top of stack is not // same as current character push the // character along with count 1 into the // top of stack st.push(new Pair(s[i], 1)); } } // iterate through the stack // Use string(int,char) in order to replicate the // character multiple times and convert into string // then add in front of output string let ans = ""; while (st.length > 0) { let c = st[st.length-1].c; let cnt = st[st.length-1].ctr; while (cnt-- > 0) ans = c + ans; st.pop(); } return ans;}// Driver codelet k = 2;let st = "neveropen";let ans = reduced_String(k, st);document.write(ans+"<br>");// This code is contributed by rag2127</script> |
Output
gksforgks
Time Complexity: O(N)
Auxiliary Space: O(N)
ANOTHER METHOD:
APPROACH:
- First we declare a Stack<Character> to store each character of the string.
- Then we iterate over the string.
- While iterating we keep a counter variable and keep pushing the character in the stack and poping simultaneously until we get a counter equals k, that implies we have got the sequence of character to remove from the string.
- At last we declare a String Builder to concatenate the characters from the stack.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;string reduced_String(int k, string s) { stack<char> stk; int i = 0; while (i < s.length()) { char ch = s[i++]; stk.push(ch); int count = 0; while (!stk.empty() && stk.top() == ch) { count++; stk.pop(); } if (count == k) continue; else { while (count > 0) { stk.push(ch); count--; } } } string result = ""; while (!stk.empty()) { result = stk.top() + result; stk.pop(); } return result;}int main() { int k = 2; string st = "neveropen"; string ans = reduced_String(k, st); cout << ans << endl; return 0;} |
C
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_SIZE 100// Function to remove k consecutive characters from the// stringchar* reduced_String(int k, char* s){ char stk[MAX_SIZE]; // Stack to store characters int top = -1; // Top index of stack int i = 0; while (s[i] != '\0') { char ch = s[i++]; stk[++top] = ch; int count = 0; while (top >= k - 1 && stk[top] == ch) { count++; top--; } if (count == k) continue; else { while (count > 0) { stk[++top] = ch; count--; } } } char* result = (char*)malloc( (top + 2) * sizeof(char)); // Allocate memory for the result int resultIndex = 0; while (top >= 0) { result[resultIndex++] = stk[top]; top--; } result[resultIndex] = '\0'; // Null-terminate the result string return result;}// Driver codeint main(){ int k = 2; char st[] = "skgrofskg"; char* ans = reduced_String(k, st); printf("%s\n", ans); free(ans); // Free the memory allocated for the result return 0;} |
Java
import java.io.*;import java.util.*;class GFG { public static String reduced_String(int k, String s) { // Your code goes here Stack<Character> stk = new Stack<Character>(); int i = 0; while (i < s.length()) { char ch = s.charAt(i++); stk.push(ch); int count = 0; while ((stk.size() > 0) && (stk.peek() == ch)) { count++; stk.pop(); } if (count == k) continue; else { while (count > 0) { stk.push(ch); count--; } } } StringBuilder sb = new StringBuilder(); for (char ch : stk) sb = sb.append(ch); return sb.toString(); } public static void main(String[] args) { int k = 2; String st = "neveropen"; String ans = reduced_String(k, st); System.out.println(ans); } }//This code is contributed by Raunak Singh |
C#
// Importing required librariesusing System;using System.Collections.Generic;class Program { // Function to reduce the string static string ReducedString(int k, string s) { // Creating an empty stack // to hold characters Stack<char> stk = new Stack<char>(); int i = 0; // Loop through each character // of the input string while (i < s.Length) { char ch = s[i++]; stk.Push(ch); int count = 0; // Count the number of consecutive // occurrences of current character while (stk.Count > 0 && stk.Peek() == ch) { count++; stk.Pop(); } // If the count is equal to k, // skip to the next character if (count == k) continue; else { // Otherwise, push back the // characters that were popped while (count > 0) { stk.Push(ch); count--; } } } // Build the final reduced string // by popping all characters // from the stack string result = ""; while (stk.Count > 0) { result = stk.Pop() + result; } return result; } // Driver Code static void Main(string[] args) { int k = 2; string st = "neveropen"; string ans = ReducedString(k, st); Console.WriteLine(ans); }} |
Javascript
// Function to reduce the stringfunction reducedString(k, s) {// Creating an empty stack to hold characters const stk = []; let i = 0;// Loop through each character of the input string while (i < s.length) { const ch = s[i++]; stk.push(ch); let count = 0;// Count the number of consecutive occurrences of current characterwhile (stk.length > 0 && stk[stk.length - 1] === ch) { count++; stk.pop();}// If the count is equal to k, skip to the next characterif (count === k) { continue;} else { // Otherwise, push back the characters that were popped while (count > 0) { stk.push(ch); count--; }}}// Build the final reduced string by popping all characters from the stack let result = ""; while (stk.length > 0) { result = stk.pop() + result;}return result;}// Driver Codeconst k = 2;const st = "neveropen";const ans = reducedString(k, st);console.log(ans); |
Output
gksforgks
Time Complexity: O(N)
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!
