Need help to remove duplicate from a string using recursion

[Winston Gutkowski]

Junilu Lacar wrote:I don't know about this one. I doubt I'd get to this code after I got the code that lined up with the unit tests. It takes me a little more effort to decipher what this is doing. The other way makes me think of finding a way to use tail recursion. This way makes me think of refactoring for clarity.

OK, well given that it's a somewhat artificial problem, my approach is slightly different. Since one of the requirements is that the solution is recursive, and recursion doesn't come naturally to me, I prefer to avoid it if I can; so I tend to look for tasks that will work for either a normal or recursive solution, and two spring to mind:
1. Find a duplicate - if this function fails then the String is fine as it is.
2. Having found a duplicate, find the end of its "group".

Between the two of them, they allow you to remove all duplicates except the last (or first) of a group, leaving the pesudo-code:
clear(str) = hasNoDuplicates(str) ? str
  : beforeDuplicates(str) + {first/last}Duplicate + clear( afterDuplicates(str) )

which is (basically) what my code does.

Don't know if it makes things any clearer, but it's the way my mind works.

Winston

[Liutauras Vilda]

Ruslan Salimych wrote:I've solved it recursively this way

That is partially recursive solution, one loop still is used.

However, that slightly violates the form recursion is being taught in general.

A recursive function normally has two parts:
1. Stopping condition. Processing the case or cases where the recursive function does not call itself.
2. Recursive step. Processing the case or cases where the recursive function calls itself.

Yours solution does not mimic that scenario. I'm not saying your solution is wrong, but worth to clarify such cases with instructor to be sure it is what expected.

[Junilu Lacar]

Winston Gutkowski wrote:
Don't know if it makes things any clearer, but it's the way my mind works.

It's clears up how your mind works ;)

It's always good to see different ways people think. Makes things more interesting. Besides, you tend to learn a lot more from seeing different points of view and different solutions to the same problem.

[Ruslan Salimovich]

Liutauras Vilda wrote:

Ruslan Salimych wrote:I've solved it recursively this way

That is partially recursive solution, one loop still is used.

Sorry, but what loop do you mean? "for" loop?

[Junilu Lacar]

BTW, I refactored to a tail-recursive version:

private String noDupes(String s) {
	if (s == null) throw new IllegalArgumentException("Parameter is null");
		
	return noDupes(s, "");
}

private String noDupes(String s, String acc) {
	if (s.length() < 2)
		return acc + s;
	
	if (s.charAt(0) != s.charAt(1))  
		acc += s.charAt(0);
		
	return noDupes(s.substring(1), acc); 
}

[Liutauras Vilda]

Ruslan Salimych wrote:Sorry, but what loop do you mean? "for" loop?

You got only one there, so it must be "for"

Being said, that recursive solution can simplify and make solution more elegant, while it is probably true, there is an other medal side - not that easy to get confident with recursive solutions, many people struggle with it, when I had to solve my first problem in recursive way there were a task to rewrite few most popular sorting algorithms in recursive way without using loops at all, I was struggling for a while, but after I got it solved and I really liked it that way.
Anyway, mixing iterative way and recursive way it just adds extra difficulty and confusion to solution (at least for me). Either you think and write in recursive way or iterative, but thinking half/half doesn't give any profit (in terms of code elegance or possible dangerous mentioned by Winston earlier in this thread).

In Java probably you always stick with iterative solutions implementing algorithms. BUT it is not something to avoid completely. There are recursive data structures which you might use everyday.

[Winston Gutkowski]

Junilu Lacar wrote:BTW, I refactored to a tail-recursive version:

I rather like that one. And if 'acc' were a StringBuilder instead of a String, I suspect it would be quite quick too.

Winston

[Junilu Lacar]

The name acc stands for accumulator, and yes, I suppose it could be a StringBuilder but that makes it mutable which is not really in line with the more functional nature it's supposed to have although I'm not even sure if the Java compiler makes optimizations for tail recursion or not. Will have to look that one up.

I guess it doesn't: http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044

[Chandler Deng]

Something like this:

	
    public String stringClean(String str) {
        return helper(str, 0, null);
	}

	private String helper(String s, int p, Character prev) {
	    if(p == s.length()) {
	        return "";
	    }
	    char c = s.charAt(p);
	    if(prev == null || !prev.equals(c)) {
	        return c + helper(s, p + 1, c);
	    }
	    else {
	        return helper(s, p + 1, c);
	    }
	}

[Junilu Lacar]

@Chandler, I haven't tested it but I guess that works. It's not how a typical recursive solution is patterned though. Your solution keeps the original string intact and just keeps passing it along on the stack. The second parameter is an index that gets incremented with each recursive call and the third parameter c looks like it's something that you could actually calculate based on the second parameter. Bottom line: it works but it could be tighter.

Recursive algorithms usually break down the original input progressively into smaller pieces until it gets to some trivial or degenerate case at which point the recursion ends and "unwinds". See the solution and the other examples for tail call recursion in the Dr Dobb's article that I cited in my last two replies.

[Chandler Deng]

Junilu Lacar wrote:@Chandler, I haven't tested it but I guess that works. It's not how a typical recursive solution is patterned though. Your solution keeps the original string intact and just keeps passing it along on the stack. The second parameter is an index that gets incremented with each recursive call and the third parameter c looks like it's something that you could actually calculate based on the second parameter. Bottom line: it works but it could be tighter.

Recursive algorithms usually break down the original input progressively into smaller pieces until it gets to some trivial or degenerate case at which point the recursion ends and "unwinds". See the solution and the other examples for tail call recursion in the Dr Dobb's article that I cited in my last two replies.

Ya I agree, can just use s.charAt(p - 1) to get the previous character. The reason that I didn't break the String is simply because of the efficiency (substring() is an O(n) operation).

[Junilu Lacar]

Chandler Deng wrote:Ya I agree, can just use s.charAt(p - 1) to get the previous character. The reason that I didn't break the String is simply because of the efficiency (substring() is an O(n) operation).

What makes you think it's O(n)? If you study the implementation at http://www.docjar.com/html/api/java/lang/String.java.html carefully, you'll see that substring() is not O(n).

This is why it's this quote is often cited: "Premature optimization is the root of all evil" --Donald Knuth

Optimization is not something you should be guessing at nor should you be thinking about it too much until you have written clear, clean code.

Edit: I stand corrected. I guess you did base your optimization on known fact. Thanks and thanks to Pawel, too.

[Paweł Baczyński]

This implementation has changed in JDK 1.7.0_06.
Now it is O(n).

The first result of my google search: link.

[Chandler Deng]

Junilu Lacar wrote:

Chandler Deng wrote:Ya I agree, can just use s.charAt(p - 1) to get the previous character. The reason that I didn't break the String is simply because of the efficiency (substring() is an O(n) operation).

What makes you think it's O(n)? If you study the implementation at http://www.docjar.com/html/api/java/lang/String.java.html carefully, you'll see that substring() is not O(n).

This is why it's this quote is often cited: "Premature optimization is the root of all evil" --Donald Knuth

Optimization is not something you should be guessing at nor should you be thinking about it too much until you have written clear, clean code.

First, this String implementation is under package java.lang while the String implementation we usually use is the java.util one. Second, even though in the java.lang.String implementation, it's still an O(n) operation -- substring actually initialize a new string and call Arrays.copyOfRange() (this is an O(n) operation) in the initialization.

Clearly you don't need to break the string in each stack so why do it when it's not free?

Edit: I think you are right, I was looking in the wrong constructor. In that implementation substring is an constant time operation since it only change the start and end pointer but share the same char array.

[Winston Gutkowski]

Chandler Deng wrote:The reason that I didn't break the String is simply because of the efficiency (substring() is an O(n) operation)...

Erm ... actually, it isn't. Or rather, it needn't be if String itself contains a start and end index - ie, all Strings are actually "substrings".

TBH, I have no idea how String is implemented these days; but I seem to remember it contained something like it in the past.

Just one reason for not optimizing too soon.

[Edit] Dang! 32 minutes too late.

Winston

[Chandler Deng]

Winston Gutkowski wrote:

Chandler Deng wrote:The reason that I didn't break the String is simply because of the efficiency (substring() is an O(n) operation)...

Erm ... actually, it isn't. Or rather, it needn't be if String itself contains a start and end index - ie, all Strings are actually "substrings".

TBH, I have no idea how String is implemented these days; but I seem to remember it contained something like it in the past.

Just one reason for not optimizing too soon.

[Edit] Dang! 32 minutes too late.

Winston

Aha, in contrast, I have no idea how String implemented at past, I begin to learn Java when it's Java 6 and at the time I paid attention to the implementation of those libraries it's already Java 7. Still, it's super cool to know the history and thanks for the information .

[Junilu Lacar]

private String noDupes(String s) {
    if (s == null) throw new IllegalArgumentException("Parameter is null");
         
    return noDupes(s, 0, new StringBuilder());
}
 
private String noDupes(String s, int i, StringBuilder acc) {
    if (s.length() - i < 2) {
        for (int x = i; x < s.length(); x++)
            acc.append(s.charAt(x));
        return acc.toString();
    }
     
    if (s.charAt(i) != s.charAt(i+1))  
        acc.append(s.charAt(i));
         
    return noDupes(s, i+1, acc); 
}

I haven't tested this yet but it incorporates the ideas that Winston and Chandler gave. It's based on the previous tail-recursive solution I gave only this doesn't use the String.substring() method. I suppose you could also use a char[] for the first parameter to the recursive method.

[Piet Souris]

The solutions are getting uglier and uglier

So here's my attempt:

public static String removeDups(String s) {
        if (s == null || s.isEmpty()) return s;
        String t = "[" + s.charAt(0) + "]+";
        Pattern pattern = Pattern.compile(t);
        Matcher matcher = pattern.matcher(s);
        matcher.find();
        return s.charAt(0) + removeDups(s.substring(matcher.end()));
    }

[Paweł Baczyński]

Piet Souris wrote:So here's my attempt

The method will fail for some inputs:

removeDups("\\");

Exception in thread "main" java.util.regex.PatternSyntaxException: Unclosed character class near index 3
[\]+

[Piet Souris]

It will be repaired in version 2.0

[Paweł Baczyński]

Streams way:

public static String removeDups(String s) {
    return s.chars()
            .distinct()
            .mapToObj(c -> String.valueOf((char) c))
            .collect(Collectors.joining());
}

[Winston Gutkowski]

Piet Souris wrote:The solutions are getting uglier and uglier
So here's my attempt:

Ie, my solution with regexes.

Gave you a tick anyway.

Winston

[Winston Gutkowski]

Paweł Baczyński wrote:Streams way

Erm, doesn't distinct() remove ALL duplicate characters? We're only trying to remove consecutive duplicates (actually, all but one).

Winston

[Paweł Baczyński]

Winston Gutkowski wrote: Erm, doesn't distinct() remove ALL duplicate characters? We're only trying to remove consecutive duplicates (actually, all but one).

Yes, it does. I feel stupid

[Piet Souris]

Winston Gutkowski wrote:

Piet Souris wrote:The solutions are getting uglier and uglier
So here's my attempt:

Ie, my solution with regexes.

Gave you a tick anyway.

Winston

hi Winston,

I honestly edited my reply so that it contained ("Winstons solution") but that somehow did not make it into the reply. Sorry! But it was indeed your solution that reminded me of a regex!

[Piet Souris]

Paweł Baczyński wrote:

Winston Gutkowski wrote: Erm, doesn't distinct() remove ALL duplicate characters? We're only trying to remove consecutive duplicates (actually, all but one).

Yes, it does. I feel stupid

Put it on the buglist, for version 2.0

[Winston Gutkowski]

Paweł Baczyński wrote:Streams way:

I'm pretty sure that:

public static String removeDups(String s) {
   int prev = Integer.MIN_VALUE;
   IntStream noDups = s.chars()
            .filter(c -> c != prev)
            .peek(c -> prev = c);
   ...
}

will create an IntStream of non-repeating "characters"; but how best to reconstitute that back to a String, I'm not sure.

Also not sure if it needs a sequential() in there or not. I suspect it might.

Hopefully Stephen is somewhere around...

Winston

[Winston Gutkowski]

Piet Souris wrote:I honestly edited my reply so that it contained ("Winstons solution") but that somehow did not make it into the reply. Sorry! But it was indeed your solution that reminded me of a regex!

I believe you; thousands wouldn't.

Winston

[Paweł Baczyński]

Winston Gutkowski wrote:will create an IntStream of non-repeating "characters"; but how best to reconstitute that back to a String, I'm not sure.

The IntStream returned is already sequential so no need to make this explicit.

Also, you'll get an error with prev variable. A variable used in lambda must be final or effectively final.

This will work:

public static String removeDups(String s) {
    AtomicInteger prev = new AtomicInteger(Integer.MIN_VALUE);
    return s.chars()
            .filter(c -> c != prev.get())
            .peek(prev::set)
            .mapToObj(c -> String.valueOf((char) c))
            .collect(Collectors.joining());
}

Or this:

public static String removeDups(String s) {
    int[] prev = new int[]{Integer.MIN_VALUE};
    return s.chars()
            .filter(c -> c != prev[0])
            .peek(c -> prev[0] = c)
            .mapToObj(c -> String.valueOf((char) c))
            .collect(Collectors.joining());
}

The array looks ugly. But it works.

Teamwork!

EDIT:
This collect looks better as it uses StringBuilder:

.peek(prev::set)
.collect(StringBuilder::new,
        (sb, i) -> sb.append((char) i),
        StringBuilder::append)
.toString();

EDIT 2:
Even better:

.peek(prev::set)
.collect(StringBuilder::new,
        StringBuilder::appendCodePoint,
        StringBuilder::append)
.toString();

Wow! This is evolving!

[Winston Gutkowski]

Paweł Baczyński wrote:Also, you'll get an error with prev variable. A variable used in lambda must be final or effectively final.

Ahh. Cheers for that. Makes perfect sense.

The String "re-creation" however seems quite convoluted and potentially very expensive, since it appears to create a new String object for each character and then join them together. Is there not a more generic way of doing it?

I have to admit, THIS is one of the things I don't like about version 8: it gives you tons of ways to generate streams, but far fewer for turning them back into regular POJOs - and the ones they do seem quite "clunky".

Strings are about as basic as it gets, so it stands to reason that if you create an IntStream from one, you might well want to convert it back, so why not just supply a toString() or asString() method?

Winston

[Winston Gutkowski]

Paweł Baczyński wrote:EDIT 2:
Even better:

.peek(prev::set)
.collect(StringBuilder::new,
        StringBuilder::appendCodePoint,
        StringBuilder::append)
.toString();

Wow! This is evolving!

Yeah, that looks much more like what I was thinking about.

I still find that collect() bit an eyesore though, but there's probably not much you can do.

Well done!

Winston

[Steffen Bauer]

I found this solution:

public class MainApp {

    public static String recursiveStringClean(String s) {

        if (s.length() <= 1)
            return "" + s.charAt(0);

        String retVal = String.valueOf(s.charAt(0));

        if ( s.charAt(0) == s.charAt(1))
            retVal = recursiveStringClean(s.substring(1));
        else
            retVal += recursiveStringClean(s.substring(1));

        return retVal;
    }

    public static String iterativeStringClean(String s) {

        StringBuilder retValue = new StringBuilder();

        char[] origin = s.toCharArray();
        char old = origin[0];
        retValue.append(old);

        for (int i = 0; i < origin.length; i++) {

            if (old == origin[i]) {
                continue;
            }
            old = origin[i];
            retValue.append(old);
        }

        return retValue.toString();
    }

    public static void main(String[] args) {

        String s1 = "yyzzza";
        System.out.printf("%s -> %s %n", s1, iterativeStringClean(s1));
        System.out.printf("%s -> %s %n", s1, recursiveStringClean(s1));


        String s2 = "abbbcdd";
        System.out.printf("%s -> %s %n", s2, iterativeStringClean(s2));
        System.out.printf("%s -> %s %n", s2, recursiveStringClean(s2));


        String s3 = "Hello";
        System.out.printf("%s -> %s %n", s3, iterativeStringClean(s3));
        System.out.printf("%s -> %s %n", s3, recursiveStringClean(s3));

    }
}

Edit: simplified condional statement in recursiveStringClean()

[Paweł Baczyński]

Winston Gutkowski wrote:Strings are about as basic as it gets, so it stands to reason that if you create an IntStream from one, you might well want to convert it back, so why not just supply a toString() or asString() method?

What would you have IntStream.of(65, 98).asString() return? 6598? Ab?
String#chars returns IntStream but those can be used for thing unrelated to strings at all.

Maybe CharacterStream (or CharStream) wouldn't be a bad idea?

[Winston Gutkowski]

Winston Gutkowski wrote:Yeah, that looks much more like what I was thinking about....

Can you do:

...
   .peek(prev::set)
   .collect(StringBuilder::new(s.length())),
      StringBuilder::appendCodePoint,
      StringBuilder::append)
   .toString();

?

That would ensure that the StringBuilder has sufficient capacity at the start. but I suspect it's too "procedural" for functional bods.

Winston

[Paweł Baczyński]

This won't work

StringBuilder::new(s.length())

If you want to pass a parameter to the constructor you need to use

() -> new StringBuilder(s.length())

[Winston Gutkowski]

Paweł Baczyński wrote:What would you have IntStream.of(65, 98).asString() return? 6598? Ab?

The latter. And what it returns is a simple documentation issue.

String#chars returns IntStream but those can be used for thing unrelated to strings at all.

Not an IntStream returned by String.chars(), it can't.

Maybe CharacterStream (or CharStream) wouldn't be a bad idea?

Precisely. But now that chars() returns an IntStream, it can't be changed.

Too much too fast, IMO. They didn't think that one through - and now we're stuck with it for all eternity.

Winston

[Winston Gutkowski]

Paweł Baczyński wrote:If you want to pass a parameter to the constructor you need to use

() -> new StringBuilder(s.length())

Ah! Sweet. Have another cow.

Winston

[Winston Gutkowski]

Steffen Bauer wrote:I found this solution:]

Hi Steffen, and welcome to JavaRanch.

And thanks for getting us back on track.

Winston

[Campbell Ritchie]

Can you have a sensible result from toString() on a Stream? A Stream is an Object, so you can use the un‑overridden version of toString, but how are you going to print its contents? A Stream does not “have” any contents; it implements lazy execution and will not contain any contents until they are required “downstream”.
I agree that a CharStream might be useful; I suspect the three kinds of primitive Stream were chosen because longs, ints and doubles are the primitive types used for arithmetic. Maybe they thought that a CharStream would be used rarely. You can probably create a Stream<Character> from an IntStream like this:-

myText.chars()
      .mapToObj(i -> Character.valueOf((char)i)
      .etc();

I am not convinced that mapToObj is the best name for that method; maybe mapToObject would have been better.
You can't readily get a character Stream from the String#toCharArray method or anything like that. In fact once I started trying out Streams I started cursing the existence of arrays of primitives. Even Arrays#stream() cannot create a character Stream from a char[]. You cannot pass that as a T[] of any sort, nor an Object[]; it would at best be considered by a varargs method as a single Object and that would produce a 1‑element array.

If you get your hands on a Stream<Character>, you can call its distinct method, but that will not convert xxyyxx to xyx. It will convert xxyyxx to xy. You can try a side‑effect with peek() and filter with i -> i != iOld, but side‑effects seem like cheating to me.

[Campbell Ritchie]

I seem to have come late to this discussion and have repeated a lot of what has been said before.