String

A string is actually an array of unicode characters.

String Comparison

String has its own compare function

Can we use "==" to compare two strings?

Depends on

Does the language support operator overloading?

Yes (like C++), we may use "==" to compare strings

No (like Java), we may not use "==" to compare two strings. "==" actually compares whether these two objects are the same object.

For Java, use

s1.equals(s2)

or

s1.compareTo(s2) == 0

Immutable or Mutable

In some languages (like C++), string is mutable, while in Java, string is immutable

Time Complexity of Built-in Operations

For instance, if the length of the string isN, the time complexity of both finding operation and substring operation isO(N).

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s1 = "Hello World";

        // 1. concatenate
        s1 += "!";
        System.out.println(s1);

        // 2. find
        System.out.println("The position of first 'o' is: " + s1.indexOf('o'));
        System.out.println("The position of last 'o' is: " + s1.lastIndexOf('o'));

        // 3. get substring
        System.out.println(s1.substring(6, 11));
    }
}

Beware of String Concatenation in Java

In Java, since the string is immutable, concatenation works by first allocating enough space for the new string, copy the contents from the old string and append to the new string.

In Java, using "+" for string concatenation, the time complexity will be O(n)

For the following, total time complexity in total will be O(n^2)

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}

Mutate String in Java

1. convert it to a char array

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "Hello World";
        char[] str = s.toCharArray();
        str[5] = ',';
        System.out.println(str);
    }
}

2. use some other data structures like StringBuilder

The below code runs in O(n) time complexity.

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        int n = 10000;
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            str.append("hello");
        }
        String s = str.toString();
    }
}