4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ What do you think is the theoretical speed of your algorithm? Do you think it is \$O(n)\$, \$O(n \log n)\$, \$O(n^2)\$, \$O(n^3)\$, or other? And what do you think the speed of the optimal solution is? \$\endgroup\$
    – JS1
    Commented Dec 27, 2016 at 10:02
  • \$\begingroup\$ Hint: try to implement it using a LinkedList of characters instead of keeping Strings. You should be able to prevent all the substring() calls. \$\endgroup\$ Commented Dec 27, 2016 at 10:32
  • \$\begingroup\$ @RobAu a working example please. \$\endgroup\$
    – CodeYogi
    Commented Dec 27, 2016 at 11:56
  • \$\begingroup\$ @JS1 my intuition says its O(n^2) since I am resetting position of i beginning after finding a duplicate pair. \$\endgroup\$
    – CodeYogi
    Commented Dec 27, 2016 at 11:58

4 Answers 4

5
\$\begingroup\$

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);
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ A very clean solution indeed, what was you thought process? \$\endgroup\$
    – CodeYogi
    Commented Dec 28, 2016 at 6:38
  • 2
    \$\begingroup\$ @CodeYogi: unstructured - documented the purpose, coded "the stack approach" using a StringBuilder, switched to char array, revised variable names, copied to CR, re-defined top from lowest invalid to highest valid, noticed I had to handle negative values of top, needed a CR user to point out that 0 was handled improperly (telling about my taking this seriously and (not) making step 2 makeshift test scaffold)… \$\endgroup\$
    – greybeard
    Commented Dec 28, 2016 at 9:07
  • \$\begingroup\$ I know there cannot be any rule but yes thinking like this helped me to solve another problem codereview.stackexchange.com/q/151023/58341 is there some kind of pattern? \$\endgroup\$
    – CodeYogi
    Commented Dec 28, 2016 at 9:44
  • \$\begingroup\$ You can use remains = input.toCharArray(); ... for (char c : remains) to avoid the creation of a not required char array. \$\endgroup\$
    – Nevay
    Commented Sep 3, 2017 at 11:43
  • \$\begingroup\$ @Nevay: looks true - I'm hesitant to mangle an iterable being iterated, even if at indices not to be re-visited by iteration. \$\endgroup\$
    – greybeard
    Commented Sep 3, 2017 at 13:22
0
\$\begingroup\$

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();
\$\endgroup\$
3
  • \$\begingroup\$ (I'd probably use a new StringBuilder encountering the first double, and append parts to keep - if I didn't go regex in the first place.) \$\endgroup\$
    – greybeard
    Commented Dec 27, 2016 at 12:54
  • \$\begingroup\$ IMHO your algorithm is not different than mine, in my case I am restarting again only when there is a duplicate pair. \$\endgroup\$
    – CodeYogi
    Commented Dec 28, 2016 at 6:32
  • \$\begingroup\$ I do a full pass, finding all the immediate ("aa") duplicate pairs in the first pass. You do partial passes, so your second and subsequent part-passes will find both immediate and non-immediate ("abba") pairs. I think that is a real difference. I also find restarting the loop partway through makes it less easy to follow the logic. YMMV. \$\endgroup\$
    – rossum
    Commented Dec 28, 2016 at 9:11
0
\$\begingroup\$

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.

\$\endgroup\$
0
0
\$\begingroup\$

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);
\$\endgroup\$
1
  • \$\begingroup\$ The formatting of your answer is broken - don't introduce every line of a non-code-block with four spaces. The question is tagged java - please mention how the code you present is to be interpreted. There are spurious white lines in your code. The indentation is broken. there seem to be more closing than opening curly braces: did this run? Please don't add answers if not entirely different: edit! \$\endgroup\$
    – greybeard
    Commented Jan 17, 2017 at 16:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.