Improving this code for reversing the string and removing duplicate characters

Question

I recently attended an interview where I was asked to write a program. The problem was:

Take a string. "Hammer", for example.
Reverse it and any character should not be repeated.
So, the output will be - "remaH".

This is the solution I gave:

public class Reverse {
    public static void main(String[] args) {
        String str = "Hammer";
        String revStr = "";

        for(int i=0; i<=str.length()-1;i++){
            if(revStr.indexOf(str.charAt(i))==-1){
                revStr = str.charAt(i)+revStr;
            }
        }
        System.out.println(revStr);
    }
}

How I can improve the above?

one thing: you are creating an awfull lot of Strings. use StringBuilder and append instead of String concatenation. if they ask you to write something, they usually want something that remains efficient when it has to deal with large input — Stultuske, May 23 '14 at 10:34
I found a similar thread on SO, which shows a much better way: http://stackoverflow.com/questions/7569335/reverse-a-string-in-java — Stultuske, May 23 '14 at 10:36
This question is probably better suited for [CodeReview](https://codereview.stackexchange.com/). — MAV, May 23 '14 at 10:36
Repeated string concatenation in Java is inefficient. Consider StringBuilder instead. Your non-repeated requirements are vague... do you mean that no character should appear more than once, or there should be no characters repeated in a row? — Matt Coubrough, May 23 '14 at 10:39
StringBuilder came to my mind while writing the code but unfortunately I though for a String reversal of 6 chars may be that wouldnt make a difference. But looks like thats what made a difference. — leo11, May 23 '14 at 11:02
Between the chars can repeat for any number of time at any place in the input string. — leo11, May 23 '14 at 11:03

amit · Accepted Answer · 2014-05-23T10:42:40.647

3

The problem is String is immutable object, and when using operator+ to concat a char with the current result, you actually create a new string.

This results in creating strings of length 1+2+...+n, which gives you total performance of O(n^2) (unless the compiler optimizes this for you).

Using a StringBuilder instead of concatting strings will give you O(n) performance, and with much better constants as well.
Note that a StringBuilder offers an efficient append() implementaiton, so you need to append elements to it, and NOT add them at the head of your StringBuilder.

You should also reconsider usage of indexOf() - if a characters cannot appear twice at all, consider using a Set<Chatacter> to maintain the list of 'used' characters, if it can appear twice, but not one after the other (for example "mam" is valid) - there is really no need for the indexOf() in the first place, just check the last character read.

edited May 23 '14 at 10:42

answered May 23 '14 at 10:37

amit

175,853
27
231
333

And it's probably better to iterate back to front on the original string and always append to the end of the buffer rather than the other way around. – biziclop May 23 '14 at 10:38
@amit so you mean indexOf is heavy operation and rather creating a Set object to maintain a used list of chars will be a better choice ? – leo11 May 23 '14 at 10:54
1

@user3588498 Yes, but depends on what you are really trying to achieve - if a character can appear twice but not one after the other (for example, "mam" is valid), than there is no need for this in the first place. Otherwise, you should use a Set to maintain the "already seen" characters in order to achieve better time performance. – amit May 23 '14 at 10:57

score 0 · Answer 2 · answered May 23 '14 at 10:59

Here is a solution without using any stringbuilder or intermediary String objects, just treating Strings as arrays of chars; this should be more efficient.

import java.util.Arrays;


public class Reverse {

  public static void main(String[] args) {
    String str = "Hammer";
    String revStr = null;

    char [] chars = str.toCharArray();
    char [] reversedChars = new char[chars.length];

    // copy first char
    reversedChars[reversedChars.length - 1] = chars[0];

    // process rest
    int r = reversedChars.length - 2;
    for(int i = 1 ; i < chars.length ; i++ ){
      if(chars[i] != chars[i-1]){
        reversedChars[r] = chars[i];
        r--;
      }
    }

    revStr = new String(Arrays.copyOfRange(reversedChars, r+1, reversedChars.length));

    System.out.println(revStr);
  }

This doesnt fix it. Suppose I use input String "ArHammerrrrrA" then I have this output "AremaHrA". So we see here that 'A' and 'r' have repeated. — leo11, May 23 '14 at 11:24
Steve, where do you see O^3 complexity?!?! This is O(n). Regarding the chars repeating, I somehow though that it was only consecutive repeating characters that were to be removed. As mentioned above, using a Set or similar would solve this part efficiently. — XSen, May 23 '14 at 11:47

Sanjay Rabari · Answer 3 · 2014-05-23T10:42:17.037

-2

package com.in.main;

public class Reverse {

public static void main(String[] args) {

    String str = "Hammer";
     StringBuilder revStr= new StringBuilder("");

    for(int i=str.length(); i>=0;i--){
        if(revStr.indexOf(str.charAt(i))==-1){
            revStr.append(str.charAt(i));
        }
    }
    System.out.println(revStr);
}

}

edited May 23 '14 at 10:42

answered May 23 '14 at 10:35

Sanjay Rabari

2,091
1
17
32

This doesn't reverse the string at all. – biziclop May 23 '14 at 10:40
Note that this will still be O(n^2), since `indexOf()` is `O(n)`, and is done iteratively. – amit May 23 '14 at 10:52

Improving this code for reversing the string and removing duplicate characters

3 Answers3