Super Reduced String

Reduce a string of lowercase characters in range ascii[‘a’..’z’]by doing a series of operations. In each operation, select a pair of adjacent letters that match, and delete them.

Delete as many characters as possible using this method and return the resulting string. If the final string is empty, return Empty String




Example:

Input:  s="aaabccddd"
Output: abd

Approach

Java

public class SuperReducedString {
    public static void main(String[] args) {
        String s = "aaabccddd";
        String result = superReducedString(s);
        System.out.println(result);
    }

    private static String superReducedString(String s) {

        while (true) {
            int n = s.length();
            for (int i = 0; i < n - 1; i++) {
                if (s.charAt(i) == s.charAt(i+1)) {
                    s=new StringBuffer(s).delete(i, i+2).toString();
                    i = i + 2;
                    n=s.length();
                }
            }
            if (s.length() == 0)
                break;
            else {
                int i = 0;
                while (i < s.length() - 1) {
                    if (s.charAt(i) != s.charAt(i+1))
                        i++;
                    else
                        break;
                }
                if (i == s.length() - 1)
                    break;
            }
        }
        if (s.length() == 0)
            return "Empty String";
        return s;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

string superReducedString(string s)
{
    while (true)
    {
        int n = s.size();
        for (int i = 0; i < n - 1; i++)
        {
            if (s[i] == s[i + 1])
            {
                s.erase(i, 2);
                i = i + 2;
            }
        }
        if (s.size() == 0)
            break;
        else
        {
            int i = 0;
            while (i < s.size() - 1)
            {
                if (s[i] != s[i + 1])
                    i++;
                else
                    break;
            }
            if (i == s.size() - 1)
                break;
        }
    }
    if (s.size() == 0)
        return "Empty String";
    return s;
}

int main()
{
    string s = "aaabccddd";
    string result = superReducedString(s);

    cout << result << "\n";

    return 0;
}