Data Structure - Strings

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 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 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

• 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

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 and JournalDev 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

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

Mutations - Concatenations

• Complete list of methods of mutate strings can be found in baeldung.

• Some methods are talked about in more detail in java67

• List of difference between + operators and concat function can be found on GeekforGeeks

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

5. Concatenation - + operation

complexity: O(n2)

+ 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
5 + 5*2 + 5*3 + 5*4 + ... + 5*n
= 5 * (1+2+3+4...+n)
= 5 * [n*(n+1)]/2
= 5 * (n 2 + n) /2
complexity = O(n2)

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)

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. ^pelligrino(On the other hand, everytime a + operator is used. a string builder object is created and original string is copied in it).