# Super Reduced String

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 Dec 27 '16 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. – RobAu Dec 27 '16 at 10:32
• @RobAu a working example please. – CodeYogi Dec 27 '16 at 11:56
• @JS1 my intuition says its O(n^2) since I am resetting position of i beginning after finding a duplicate pair. – CodeYogi Dec 27 '16 at 11:58

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;

: new String(remains, 0, top+1);
}

• A very clean solution indeed, what was you thought process? – CodeYogi Dec 28 '16 at 6:38
• @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)… – greybeard Dec 28 '16 at 9:07
• 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? – CodeYogi Dec 28 '16 at 9:44
• You can use remains = input.toCharArray(); ... for (char c : remains) to avoid the creation of a not required char array. – Nevay Sep 3 '17 at 11:43
• @Nevay: looks true - I'm hesitant to mangle an iterable being iterated, even if at indices not to be re-visited by iteration. – greybeard Sep 3 '17 at 13:22

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

• (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.) – greybeard Dec 27 '16 at 12:54
• IMHO your algorithm is not different than mine, in my case I am restarting again only when there is a duplicate pair. – CodeYogi Dec 28 '16 at 6:32
• 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. – rossum Dec 28 '16 at 9:11

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.

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

• 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! – greybeard Jan 17 '17 at 16:53