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.

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? — JS1
– JS1, Commented Dec 27, 2016 at 10:02
Hint: try to implement it using a LinkedList of characters instead of keeping Strings. You should be able to prevent all the substring() calls. — Rob Audenaerde
– Rob Audenaerde, Commented Dec 27, 2016 at 10:32
@JS1 my intuition says its O(n^2) since I am resetting position of i beginning after finding a duplicate pair. — CodeYogi
– CodeYogi, Commented Dec 27, 2016 at 11:58

greybeard · Accepted Answer · 2016-12-27 19:04:46Z

6

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);
}

edited Dec 27, 2016 at 19:04

answered Dec 27, 2016 at 13:40

greybeard

7,8193 gold badges21 silver badges56 bronze badges

1

\$\begingroup\$ A very clean solution indeed, what was you thought process? \$\endgroup\$

CodeYogi
– CodeYogi

2016-12-28 06:38:02 +00:00
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
– greybeard

2016-12-28 09:07:26 +00:00
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
– CodeYogi

2016-12-28 09:44:04 +00:00
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
– Nevay

2017-09-03 11:43:09 +00:00
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
– greybeard

2017-09-03 13:22:55 +00:00
Commented Sep 3, 2017 at 13:22

Add a comment |

rossum · Accepted Answer · 2016-12-27 12:38:09Z

0

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();

answered Dec 27, 2016 at 12:38

rossum

6354 silver badges13 bronze badges

\$\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
– greybeard

2016-12-27 12:54:36 +00:00
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
– CodeYogi

2016-12-28 06:32:52 +00:00
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
– rossum

2016-12-28 09:11:13 +00:00
Commented Dec 28, 2016 at 9:11

Add a comment |

greybeard · Accepted Answer · 2017-01-17 17:13:42Z

0

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.

edited Jan 17, 2017 at 17:13

greybeard

7,8193 gold badges21 silver badges56 bronze badges

answered Dec 27, 2016 at 10:06

Timothy Truckle

7,29115 silver badges24 bronze badges

Add a comment |

Nisse Engström · Accepted Answer · 2017-09-02 21:54:08Z

0

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);

edited Sep 2, 2017 at 21:54

Nisse Engström

1091 silver badge5 bronze badges

answered Jan 17, 2017 at 16:41

Vivek Mehta

1013 bronze badges

\$\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
– greybeard

2017-01-17 16:53:05 +00:00
Commented Jan 17, 2017 at 16:53

Add a comment |

Stack Exchange Network

Super Reduced String

Problem Statement

Input Format

Constraints

Output Format

Sample Input

Sample Output

Solution Code

4 Answers 4

You must log in to answer this question.

Linked

Hot Network Questions

Super Reduced String

Problem Statement

Input Format

Constraints

Output Format

Sample Input

Sample Output

Solution Code

4 Answers 4

You must log in to answer this question.

Linked

Related

Hot Network Questions