java – Hackerrank string reduction

java – Hackerrank string reduction

Your problem is that:

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

You only look at your first character until you cant 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);
} 

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

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.

java – Hackerrank string reduction

Leave a Reply

Your email address will not be published. Required fields are marked *