Hackerrank string reduction

Question

I am working on the following problem https://www.hackerrank.com/challenges/reduced-string .

I want to solve the above problem recursively . My code is as follows .

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(neInputStreamReader(System.in));
        String line = br.readLine();
        System.out.print(reduce(line));  
    }

    public static String reduce (String str) {
        if (str.equals("")) return "Empty String";
        if (str.length()<2) return str;
        if (str.charAt(0) == str.charAt(1)) return reduce(str.substring(2));
        return str.charAt(0) + reduce(str.substring(1));
    } 
}

The above code fails for the following test case
baab

Could any one point out what is the problem in my code ?

Possible duplicate of [What is a debugger and how can it help me diagnose problems?](http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Raedwald, Sep 26 '16 at 08:40
**Doesn't work** is an insufficient description if you want us to help you. — GhostCat, Sep 26 '16 at 08:41

score 0 · Answer 1 · answered Sep 26 '16 at 08:51

0

str.charAt(0)+reduce(str.substring(1));

What if charAt(0) becomes equal with the first char of str.substring(1)? You finish with an unreduced pair.

answered Sep 26 '16 at 08:51

Adrian Colomitchi

3,974
1
14
23

score 0 · Accepted Answer · answered Sep 26 '16 at 08:55

Your problem is that:

reduce("baab") = 'b' + reduce("aab") = 'b' + reduce("b") = 'b' + 'b' = "bb"

You only look at your first character until you can't immediately remove it anymore. Then you never look at it again, even if at some point afterwards you actually could remove it.

I suppose you could do something like this instead:

public static String reduce(String str){
    if(str.equals(""))
        return "Empty String";
    if(str.length()<2)
        return str;
    if(str.charAt(0)==str.charAt(1))
        return reduce(str.substring(2));

    String rest = str.substring(1);
    String reducedRest = reduce(rest);

    if (rest.equals(reducedRest)) 
        return str;
    else 
        return reduce(str.charAt(0) + reducedRest);
}

It's not great but it should show you the general idea. Now you only ignore the first char if you don't change the rest. If you do change it, you need to look at the whole thing again.

Please keep in mind that it's not the most efficient way to do this. In case the reducedRest actually is a reduced rest (meaning it really was reduced), you technically only need to see if your first two characters can now be removed. But whether you can remove them or not there's actually no need to recheck the remaining string. — Mark, Sep 26 '16 at 09:09

Hackerrank string reduction

2 Answers2