Remove a Character From String in Java-CodePudding

I'm trying to concatenate a string with itself and remove capital letters from the resultant string.

Here is my code:

public String removeCapitals(String A) {
    StringBuilder B = new StringBuilder(A A);
    int n = B.length();

    for(int i=0; i<n; i  ){
        if(B.charAt(i)>='A' && B.charAt(i)<='Z'){
            B.deleteCharAt(i);
        }
    }

    return B.toString();
}

I'm getting Exception saying:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 6
at java.lang.AbstractStringBuilder.charAt(AbstractStringBuilder.java:237)
at java.lang.StringBuilder.charAt(StringBuilder.java:76)
at Solution.removeCapitals(Solution.java:10)
at Main.main(Main.java:190)

Can someone help me understand the issue.

CodePudding user response：

When you delete a character you change the length of the StringBuilder. But n still has the original length. So you will eventually exceed the size of the StringBuilder. So start from the end and move backwards. That way, any deletions will come after (based on relative indices) the next position so the index will be within the modified StringBuilder size. In addition, deleting from the end is more efficient since there is less copying to do in the StringBuilder.

public String removeCapitals(String A) {
    StringBuilder B = new StringBuilder(A A);
    int n = B.length(); 

    for(int i=n-1; i>=0; i--){
        if(B.charAt(i)>='A' && B.charAt(i)<='Z'){
            B.deleteCharAt(i);
        }
    }

    return B.toString();
}

CodePudding user response：

If at least one removal succeeds, at some point your code will attempt to access an invalid index that exceeds the length of a StringBuilder.

It happens because the variable n remain unchanged. You should change the condition to be bound to the current size of StringBuilder and decrement the index at each removal, or iterate backwards (as shown in another answer).

Also condition B.charAt(i)>='A' && B.charAt(i)<='Z' can be replaced with:

Character.isUpperCase(b.charAt(i))

Which is more descriptive.

That's how it might look like:

 public static String removeCapitals(String a) {
    
    StringBuilder b = new StringBuilder(a   a);
    
    for (int i = 0; i < b.length(); i  ) {
        if (Character.isUpperCase(b.charAt(i))) {
            b.deleteCharAt(i); // which can be combined with the next line `b.deleteCharAt(i--);` - previous value of `i` would be used in the call `deleteCharAt()` and variable `i` will hold a value decremented by 1
            i--;
        }
    }
    return b.toString();
}

Method deleteCharAt() runs in a linear time, because it shifts all subsequent characters in the underlying array bytes. Each upper-case letter will trigger these shifts and in the worst case scenario, it would result in the quadratic over time complexity.

You make your method more performant and much more concise without using loops and StringBuilder.

public static String removeCapitals(String a) {
    
    return a.replaceAll("\\p{Upper}", "").repeat(2);
}