Strings

String

One of the fundamental data type in Computer Since, which is basically an array of integers under the hood, where each character in a given string is mapped to an integer via some character-encoding standard like ASCII.

We can divide Strings to mutable and immutable, in most languages they are immutable, meaning that they can’t be edited after creation. So as you can imagine, simple operations like appending a character to a string would be more expensive than it might appear.

The canonical example of an operation that’s deceptively expensive due to string immutability is the following:

String someString = "some string";
String newString = "";
for (char character : someString.toCharArray()) {
	  newString += character;
}

The operation above has a time complexity O(n²) where n is the length of ‘someString’, because each addition of a character to newString creates an entirely new string and is itself an O(n) operation, but keep in mind that n O(n) operations are performed (O(n) for each character in given string), which is leading to an O(n²) time-complexity operation at the end.