III. String Manipulation:

String manipulation problems are not much different from array traversal, as a string is consists of an array of characters.

However, there are some differences that you need to be aware of when dealing with String.

String is immutable in Java

First, String object is immutable in Java, unlike C++. String is also immutable in Python. That means you can't change the content of the string once it's initialized. For example, this is valid in C++ but is invalid in Java:

In C++, string is mutable and you can change its content:

string s = "hello";
s[0] = 'j';
cout << s << endl;   // prints "jello"

In Java, string is immutable:

String s = "hello";
s[0] = 'j';   // Compile error: array required, but String found

Of course, you can change the content of the string if it is converted to a char[] array, but it would incur extra space:

String s = "hello";
char[] str = s.toCharArray();
str[0] = 'j';
System.out.println(str);   // prints "jello"

Beware of string concatenation

The following simple Java code does string concatenation a total of times. What is the time complexity?

String s = "";
for (int i = 0; i < n; i++) {
    s += "hello";

If you think it is , you are wrong! It actually runs in . Since string is immutable in Java, concatenation works by first allocating enough space for the new string, copy the contents from the old string and append to the new string. Therefore, the number of operations is:

Therefore, be mindful if you are doing string concatenation in a loop. To concatenate string efficiently, just use StringBuilder, which is a mutable object. The below code runs in complexity.

StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) {