# 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 is`N`, the time complexity of both finding operation and substring operation is`O(N)`.

```java
// "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)**

```java
// "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

```java
// "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.**

```java
// "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();
    }
}
```