How to efficiently remove consecutive same characters in a string

user_3099648 0
Viewed 1202

I wrote a method to reduce a sequence of the same characters to a single character as follows. It seems its logic is correct while there is a room for improvement in terms of performance, according to my tutor. Could anyone shed some light on this? Comments of aspects other than performance is also really appreciated.

public class RemoveRepetitions {
    public static String remove(String input) {
        String ret = "";
        String last = "";
        String[] stringArray = input.split("");

        for(int j=0; j < stringArray.length; j++) {
            if (! last.equals(stringArray[j]) ) {
                ret += stringArray[j];
            }
            last = stringArray[j];
        }

        return ret;
    }

    public static void main(String[] args) {
        System.out.println(RemoveRepetitions.remove("foobaarrbuzz"));
    }
}
java string
3 Answers

We can improve the performance by using StringBuilder instead of using string as string operations are costlier. Also, the split function is also not required (it will make the program slower as well). Here is a way to solve this:

public static String remove(String input)
{
    StringBuilder answer = new StringBuilder("");
    int N = input.length();
    int i = 0;

    while (i < N)
    {
        char c = input.charAt(i);
        answer.append( c );
        while (i<N && input.charAt(i)==c)
            ++i;
    }
    return answer.toString();
}

The idea is to iterate over all characters of the input string and keep appending every new character to the answer and skip all the same consecutive characters.

user_138824250

Possible change which you could think of in your code is:

Time Complexity: Your code is achieving output in O(n) time complexity, which might be the best possible way.

Space Complexity: Your code is using extra memory space which arises due to splitting.

Question to ask: Can you achieve this output, without using the extra space for character array that you get after splitting the string? (as character by character traversal is possible directly on string).

I can provide you the code here but, it would be great if you could try it on your own, once you are done with your attempts

you can lookup for the best solution here (you are almost there) https://www.geeksforgeeks.org/remove-consecutive-duplicates-string/

Good luck!

user_25512360

As mentioned before, it is much better to access the characters in the string using method String::charAt or at least by iterating a char array retrieved with String::toCharArray instead of splitting the input string into String array.

However, Java strings may contain characters exceeding basic multilingual plane of Unicode (e.g. emojis , Chinese or Japanese characters etc.) and therefore String::codePointAt should be used. Respectively, Character.charCount should be used to calculate appropriate offset while iterating the input string.

Also the input string should be checked if it's null or empty, so the resulting code may look like this:

public static String dedup(String str) {
    if (null == str || str.isEmpty()) {
        return str;
    }
    int prev = -1;
    int n = str.length();
    System.out.println("length = " + n + " of [" + str + "], real length: " + str.codePointCount(0, n));
    
    StringBuilder sb = new StringBuilder(n);
    
    for (int i = 0; i < n; ) {
        
        int cp = str.codePointAt(i);

        if (i == 0 ||  cp != prev) {
            sb.appendCodePoint(cp);
        }
        prev = cp;
        i += Character.charCount(cp); // for emojis it returns 2
    }
    
    return sb.toString();
}

A version with String::charAt may look like this:

public static String dedup2(String str) {
    if (null == str || str.isEmpty()) {
        return str;
    }
    int n = str.length();
    StringBuilder sb = new StringBuilder(n);
    sb.append(str.charAt(0));
    
    for (int i = 1; i < n; i++) {
        if (str.charAt(i) != str.charAt(i - 1)) {
            sb.append(str.charAt(i));
        }
    }
    
    return sb.toString();
}

The following test proves that charAt fails to deduplicate repeated emojis:

System.out.println("codePoint: " + dedup (" hello"));
System.out.println("charAt:    " + dedup2(" hello"));

Output:

length = 20 of [ hello], real length: 13
codePoint:  helo
charAt:     helo
user_132798310
Related