Data Structure - Strings
Published: 2021-03-04 14:33:10

# Strings

> array of unicode characters

## Functions

### 1. find
complexity: `O(N)`

```
System.out.println("The position of first 'o' is: " + s1.indexOf('o')); // 4
System.out.println("The position of last 'o' is: " + s1.lastIndexOf('o')); // 7
```
### 2. substring
Complexity: `O(N)`

N is length of string. 
String.substring(`i`,`j`) gets characters from indexes `i` to `j-1` inclusive.
```
System.out.println(s1.substring(6, 11)); // World
```

## Comparing Strings
In Java you **cannot** use `==` operator to compare strings. 

> Can use `==` to compare strings? -> **depends on** 
Does language support `operator overloadig`? 

1. `yes` : can use `==`
2. `no` (for Java) : cannot

In Java `==` compares object's memory address. Comparing two string objects will be false
```
String s1 = new String("HELLO"); 
String s2 = new String("HELLO"); 
  
System.out.println(s1 == s2);  // false
```

Java's [String Pool](https://www.journaldev.com/797/what-is-java-string-pool) is why `==` is true when comparing string literals

```
String s1 = "Cat";
String s2 = "Cat";
String s3 = new String("Cat");
        
System.out.println(s1==s2); // true
System.out.println(s1 == s3); // false
```

##### Operator Overloading
> [Operator overloading](https://blogs.oracle.com/javamagazine/is-it-time-for-overloading-in-java) allows language operators to have user-defined meanings on user-defined types / classes.

If user defined a class `Foo` user is able to define an implementation for the plus (`+`) operator such that `FooBar = Foo + Bar`

##### Java String Pool
More details about Java String Pool can be found on [baeldung](https://www.baeldung.com/java-string-pool)

- String Interning

Since Strings in Java are immutable, JVM optimizes memory allocated for strings by storing only one copy of each String literal in the String pool This is known as *String Interning*.

When String literal is created, JVM searches pool for a string of equal value.
- Found

compiler returns reference to its memory address without allocatin additional memory
- Not Found

literal is added to the pool (interned) and its reference will be returned

String pool is an exmaple of [Flyweight Design Pattern](https://www.tutorialspoint.com/design_pattern/flyweight_pattern.htm)

### 3. String.compareTo

> compare strings lexicographically (same length & have contain same characters in same positions)

function converts each character of strings to unicode value for comparison. 
- `<0`: the String calling the method is lexicographically first (comes first in a dictionary)
- `== 0`:  strings are lexicographically equivalent
- `>0`: the parameter passed to the compareTo method is lexicographically first.

### 4. String.equalsTo

> compares the two given strings based on the data/content of the string.

## Modifying Strings

## Immutable
Java string is **immutable**.

> `Immutable`: user can't change content of string once its initialized. However new string can be created. 

[Baeldung](https://www.baeldung.com/java-string-immutable) and [JournalDev](https://www.journaldev.com/802/string-immutable-final-java) articles list reasons why strings are immutable in Java.

**NOTE**
> while `String` object is immutable, its reference variable is NOT. reference variable can be made to refer to a new string object

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jyonqry6o3ih6d0e90u5.png)
 
As seen from image above, String ("Hello") is not changed / modified, so a new String ("Hello World") is created instead. 

```
String s="Hello";  
s.concat(" World"); 
System.out.println(s); // prints 'Hello' since strings are immutable objects  
```
**NOTE**
> The string *Hello* is lost. However the object still **exists in string pool**, object is considered lost due to having no reference. 

Reference variable is mutable. Hence, Java can assign the reference `s` a new value "Hello World".

```
String s="Hello";  
s=s.concat(" World"); 
System.out.println(s); // prints 'Hello World' since new strig object is assigned to s. 
```

**NOTE**
> At this point we technically have **three** String objects. 1) initial object "Hello" 2) New object created "Hello World" & 3) the literal " World" in the concat statement. 

More details about Java string immutable can be found on [GeekForGeeks](https://www.geeksforgeeks.org/java-string-is-immutable-what-exactly-is-the-meaning/)

## Mutations - Concatenations
- Complete list of methods of mutate strings can be found in [baeldung](https://www.baeldung.com/java-strings-concatenation).
- Some methods are talked about in more detail in [java67](https://www.java67.com/2015/05/4-ways-to-concatenate-strings-in-java.html)

- List of difference between `+` operators and concat function can be found on [GeekforGeeks](https://www.geeksforgeeks.org/difference-between-concat-and-operator-in-java/)

Below discussions about complexity / performance will be in relation to concatenating a BUNCH of strings. 

### 5. Concatenation - `+` operation
complexity: <code>O(n<sup>2</sup>)</code>

`+` is actually the worst way to concat strings. **NEVER** use them in a loop.

Concatenation works by first allocating enough space for the new string, copying contents from old string and appending to the ew string.
```
String s = "";
int n = 10000;
for (int i = 0; i < n; i++) {
    s += "hello"; // or s.concat("hello");
}
```
Complexity calculation
<code> 5 + 5*2 + 5*3 + 5*4 + ... + 5*n 
 = 5 * (1+2+3+4...+n)
 = 5 * [n*(n+1)]/2
 = 5 * (n <sup>2</sup> + n) /2 </code>
complexity = <code> O(n<sup>2</sup>) </code>

Under the hood, `+` operators translate to `StringBuilder.append()` before a final `.toString()` call. 
So 1 to `+` two strings you need.
- 1 StringBuilder
- 1 String object (output) ("AB"
- initial String ("A")
- input String ("B")

```
String temp = "A"+"B";
new StringBuilder().append("A").append("B").toString();

```
### 6. String.concat(String input)
String.concat returns a string, so user can chain concat operations.

- better than `+` operator because concat is more strict in what is accepts (detailed answer [here](https://stackoverflow.com/a/47628))

concat
1. only accepts inputs of type String
2. throws NullPointerException if input is null
3. only returns new String object is input.length > 0

```
String s = "Geeks", g = ""; 
String f = s.concat(g);
System.out.println(f == s); // true
// length of g is 0, so s.concat(g) returns s
String e = s + g;
System.out.println(e == s); // false
// + returns a new string object
```

### 7.StringBuffer

> internally maintains array of characters `char[]`. 

**OLD: do not use this** (unless you have multiple threads accessing string)
to create mutable string
- thread safe.
- lower performance (then string builder)

### 8.String.toCharArray()
complexity: `O(N)`
N is length of string - copy each char of string into array. 
Convert string to char array and mutate
```
String s = "Hello World";
char[] str = s.toCharArray();
str[5] = ',';
```

### 9.StringBuilder

> internally maintains mutable array (ArrayList) of characters 

- NOT thread safe
- faster then string buffer (therefore preferred) 
- preferred options if you are concatenating a BUNCH of strings (like in a loop)

complexity: `O(N)`
```
int n = 10000;
StringBuilder str = new StringBuilder();
for (int i = 0; i < n; i++) {
    str.append("hello");
}
String s = str.toString();
```
In StringBuilder, append alters the state of the object thus avoiding several copies. <sup>[pelligrino](https://pellegrino.link/2015/08/22/string-concatenation-with-java-8.html)</sup>(On the other hand, everytime a `+` operator is used. a string builder object is created and original string is copied in it).