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 = “geeksforgeeks”
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:
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solution {
public :
string remove_k_char( int k, string s)
{
if (k == 1)
return "" ;
string output = "" ;
stack<pair< char , int > > stk;
for ( int i = 0; i < s.length(); i++) {
if (stk.empty() == true ) {
stk.push(make_pair(s[i], 1));
}
else {
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 {
stk.push(make_pair(s[i], 1));
}
}
}
while (!stk.empty()) {
if (stk.top().second > 1) {
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;
}
};
int main()
{
string s = "geeksforgeeks" ;
int k = 2;
Solution obj;
cout << obj.remove_k_char(k, s) << "\n" ;
return 0;
}
|
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[] = "geeksforgeeks" ;
int k = 2;
char * result = remove_k_char(k, s);
printf ( "%s\n" , result);
free (result);
return 0;
}
|
Java
import java.util.*;
class GFG {
public static String reduced_String( int k, String s)
{
if (k == 1 ) {
return "" ;
}
Stack<Pair> st = new Stack<Pair>();
int l = s.length();
int ctr = 0 ;
for ( int i = 0 ; i < l; i++) {
if (st.size() == 0 ) {
st.push( new Pair(s.charAt(i), 1 ));
continue ;
}
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 ));
}
}
StringBuilder output = new StringBuilder();
while (st.size() > 0 ) {
char c = st.peek().c;
int cnt = st.peek().ctr;
while (cnt-- > 0 )
output.append(String.valueOf(c));
st.pop();
}
output.reverse();
return output.toString();
}
public static void main(String[] args)
{
int k = 2 ;
String st = "geeksforgeeks" ;
String ans = reduced_String(k, st);
System.out.println(ans);
}
static class Pair {
char c;
int ctr;
Pair( char c, int ctr)
{
this .c = c;
this .ctr = ctr;
}
}
}
|
Python3
class Pair:
def __init__( self ,c ,ctr):
self .c = c
self .ctr = ctr
class Solution:
def reduced_String( self , k , s):
if (k = = 1 ):
return ""
st = []
for i in range ( len (s)):
if ( len (st) = = 0 ):
st.append((Pair(s[i] , 1 )))
continue
if (st[ - 1 ].c = = s[i]):
pair = st.pop()
pair.ctr + = 1
if (pair.ctr = = k):
continue
else :
st.append(pair)
else :
st.append((Pair(s[i] , 1 )))
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)
if __name__ = = "__main__" :
k = 2
s = "geeksforgeeks"
obj = Solution()
print (obj.reduced_String(k,s))
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public static String reduced_String( int k, String s)
{
if (k == 1) {
return "" ;
}
Stack<Pair> st = new Stack<Pair>();
int l = s.Length;
for ( int i = 0; i < l; i++) {
if (st.Count == 0) {
st.Push( new Pair(s[i], 1));
continue ;
}
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 {
st.Push( new Pair(s[i], 1));
}
}
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;
}
public static void Main(String[] args)
{
int k = 2;
String st = "geeksforgeeks" ;
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;
}
}
}
|
Javascript
<script>
class Pair
{
constructor(c,ctr)
{
this .c = c;
this .ctr = ctr;
}
}
function reduced_String(k,s)
{
if (k == 1) {
let ans = "" ;
return ans;
}
let st = [];
let l = s.length;
let ctr = 0;
for (let i = 0; i < l; i++) {
if (st.length == 0) {
st.push( new Pair(s[i], 1));
continue ;
}
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 {
st.push( new Pair(s[i], 1));
}
}
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;
}
let k = 2;
let st = "geeksforgeeks" ;
let ans = reduced_String(k, st);
document.write(ans+ "<br>" );
</script>
|
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 = "geeksforgeeks" ;
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
char * reduced_String( int k, char * s)
{
char stk[MAX_SIZE];
int top = -1;
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 ));
int resultIndex = 0;
while (top >= 0) {
result[resultIndex++] = stk[top];
top--;
}
result[resultIndex]
= '\0' ;
return result;
}
int main()
{
int k = 2;
char st[] = "skgrofskg" ;
char * ans = reduced_String(k, st);
printf ( "%s\n" , ans);
free (ans);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static String reduced_String( int k, String s)
{
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 = "geeksforgeeks" ;
String ans = reduced_String(k, st);
System.out.println(ans);
}
}
|
C#
using System;
using System.Collections.Generic;
class Program {
static string ReducedString( int k, string s)
{
Stack< char > stk = new Stack< char >();
int i = 0;
while (i < s.Length) {
char ch = s[i++];
stk.Push(ch);
int count = 0;
while (stk.Count > 0 && stk.Peek() == ch) {
count++;
stk.Pop();
}
if (count == k)
continue ;
else {
while (count > 0) {
stk.Push(ch);
count--;
}
}
}
string result = "" ;
while (stk.Count > 0) {
result = stk.Pop() + result;
}
return result;
}
static void Main( string [] args)
{
int k = 2;
string st = "geeksforgeeks" ;
string ans = ReducedString(k, st);
Console.WriteLine(ans);
}
}
|
Javascript
function reducedString(k, s) {
const stk = [];
let i = 0;
while (i < s.length) {
const ch = s[i++];
stk.push(ch);
let count = 0;
while (stk.length > 0 && stk[stk.length - 1] === ch) {
count++;
stk.pop();
}
if (count === k) {
continue ;
} else {
while (count > 0) {
stk.push(ch);
count--;
}
}
}
let result = "" ;
while (stk.length > 0) {
result = stk.pop() + result;
}
return result;
}
const k = 2;
const st = "geeksforgeeks" ;
const ans = reducedString(k, st);
console.log(ans);
|
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 geeks!