Strings

Question 1

Basics

Answer 1

• It’s represented as an array of integers (ASCII values of each character) in memory
• In some languages Strings are mutable and in others, like Java, are immutable
• Immutable Strings:
  * When going to mutate a String, it’s better to convert it to an array of characters to have constant operations when appending/removing characters at the end
  * Setting a character in a String is not possible because of immutability

Question 2

Space-time complexities 1

Answer 2

• Every operation done to a single character of a string is a constant operation. They’re O(1) ST
• Traversing a string is a linear operation. It’s O(N) T, O(1) S
• Copying a string is a linear operation. It’s O(N) ST

Question 3

Space-time complexities 2

Answer 3

• Accessing a character of a string is a constant operation. It’s O(1) ST
• Mutating a string is a linear operation. It’s O(N) ST
• Initializing a string is a linear operation. It’s O(N) ST