Super Reduced String

Question

Online challenge on Hacker Rank.

Problem Statement

Steve has a string, S, consisting of n lowercase English alphabetic >letters. In one operation, he can delete any pair of adjacent letters with same >value. For example, string "aabcc" would become either "aab" or "bcc" >after operation.

Steve wants to reduce as much as possible. To do this, he will repeat the >above operation as many times as it can be performed. Help Steve out by finding >and printing S's non-reducible form!

Note: If the final string is empty, print Empty String.

Input Format

A single string, S.

Constraints

\$1 ≤ n ≤ 100\$

Output Format

If the final string is empty, print Empty String; otherwise, print the final >non-reducible string.

Sample Input

aaabccddd

Sample Output

abd

---

Solution Code

public class Solution {
    private static String solve(String input) {
        int len = input.length();

        int i = 0;
        while (i < len - 1) {
            char current = input.charAt(i);
            char next = input.charAt(i+1);

            if (current == next) {
                input = input.substring(0, i) + input.substring(i+2);
                len = input.length();
                i = 0;
                continue;
            }
            i++;
        }
        if (input.length() == 0) {
            return "Empty String";
        }
        return input;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println(solve(s.next()));
    }
}

This is a brute-force solution, as I feel kind of confused when dealing with string algorithms. Hope for some good suggestions here.

Answer 1

Doc comments for public methods are indispensable.

I'd probably just use a foreach-loop and a DIY stack:

/** @return input stripped of all abutting identical characters */
static String solve(String input) {
    char []remains = new char[input.length()];
    int top = -1; // highest valid index

    for (char c: input.toCharArray())
        if (top < 0 || c != remains[top])
            remains[++top] = c;
        else
            --top;

    return top < 0 ? "Empty String"
        : new String(remains, 0, top+1);
}

Answer 2

Two suggestions. First, you are restarting your loop part-way through the string and resetting i to 0. That means you are checking the first part of the string more than once. For input like "abbccddeeff" you will be checking the "a" five times. Instead, do a full pass with the loop and then do another full pass only if needed. Separating the loop logic into two loops seems clearer to me as well.

Second, since most of the work will be deleting characters from strings, I think that using a StringBuilder would help, specifically the StringBuilder.delete(a, b) method.

private static String solve(String input) {

    StringBuilder insb = new StringBuilder(input);

    boolean passNeeded = true;

    while (passNeeded) {

        passNeeded = false;

        // Do a single full pass.
        for (int i = 0; i < insb.length() - 1; ++i) {
            char current = insb.charAt(i);
            char next = insb.charAt(i+1);

            if (current == next) {
                insb = insb.delete(i, i+2);

                // Text has changed so another pass needed.
                passNeeded = true;
            }

        } // end for

    } // end while

    if (insb.length() == 0) {
        return "Empty String";
    }

    return insb.toString();

} // end solve();

Answer 3

IMHO your solution looks quite good. There would be a solution using regular expressions but I think your solution fits better the plan of your course...

---

The only thing I'd change is the continue within your while loop.

continue and break (within loops) are the "poor man's goto" and should be avoided since they harm readability of your code and make refactoring harder.

So instead of continue simply use else to skip i++ when your condition is met.

Answer 4

As it was mentioned in the question that you have to remove the repetitive elements inside the string, so firstly we will convert it to an Array, then we will compare it with every next element of that Array, if it is equal to 0 then we have to splice the respective two elements from Array and initially we will put a while condition so that it will iterate through the loop every possible time.

var string = input.split('');
var result;

var Boolean = (1);

while (Boolean) {

    Boolean = (0);

    for (var i = 0; i <= string.length - 1; i++) {
        if(string[i] == string[i + 1]){
            string.splice(i, 2);


            result = string.join("");
            Boolean = (1);
            if(string.length == 0){
                result = "Empty String";
            }
        }
    }
}
console.log(result);