Reduce the string by removing K consecutive identical characters

0 0 11 minutes read

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 = “zambiatek”
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 1
 
class 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 Code
int main()
{
 
    string s = "zambiatek";
    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[] = "zambiatek";
    int k = 2;
 
    char* result = remove_k_char(k, s);
    printf("%s\n", result);
 
    free(result);
 
    return 0;
}

Java

// Java implementation of the approach
import 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 = "zambiatek";
        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 freq
class Pair:
    def __init__(self,c ,ctr):
        self.c= c
        self.ctr = ctr
 
class 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 code
if __name__ == "__main__":
     
    k = 2
    s = "zambiatek"
    obj = Solution()
    print(obj.reduced_String(k,s))
 
    # This code is contributed by chantya17.

C#

// C# implementation of the above approach
using 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 = "zambiatek";
        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 approach
 
class Pair
{
    constructor(c,ctr)
    {
        this.c = c;
            this.ctr = ctr;
    }
}
 
// Function to find the reduced string
function 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 code
let k = 2;
let st = "zambiatek";
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 = "zambiatek";
    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
// string
char* 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 code
int 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 = "zambiatek";
          String ans = reduced_String(k, st);
          System.out.println(ans);
      }
  }
//This code is contributed by Raunak Singh

C#

// Importing required libraries
using 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 = "zambiatek";
 
        string ans = ReducedString(k, st);
 
        Console.WriteLine(ans);
    }
}

Javascript

// Function to reduce the string
function 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 character
while (stk.length > 0 && stk[stk.length - 1] === 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
 let result = "";
 while (stk.length > 0) {
 result = stk.pop() + result;
}
 
return result;
}
 
// Driver Code
const k = 2;
const st = "zambiatek";
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 zambiatek!