Module Review: Strings

Key Takeaways

  1. Immutability: In Java and Go, strings are immutable. Any modification creates a new object. This is crucial for thread safety and security.
  2. Builders: Always use StringBuilder (Java) or strings.Builder (Go) for concatenating strings in a loop to avoid O(N<sup>2</sup>) memory allocation behavior.
  3. Memory Layout: Java strings store a byte array and coder. Go strings are a pointer and a length.
  4. Searching: The Naive approach checks every position (O(N*M)). Advanced algorithms like KMP use preprocessing to achieve linear time (O(N)).
  5. Techniques: Sliding Window and Two Pointers are the most common patterns for solving string problems (substrings, palindromes, anagrams).

Interactive Flashcards

Test your knowledge with these flashcards. Click to flip.

What is the time complexity of string concatenation using `+` in a loop of N iterations?
O(N2) because each iteration copies the growing string.
Why are strings immutable in Java and Go?
Security (cannot be changed by malicious code), Thread Safety, and efficient sharing (String Pool).
What is the space complexity of a Naive String Search?
O(1) because it only requires a few integer variables for indices, regardless of input size.
What data structure creates a mutable string buffer in Go?
strings.Builder (or a []byte slice).
Does s.substring() in modern Java copy the underlying array?
Yes. Since Java 7u6, it creates a new byte array to prevent memory leaks where a small substring keeps a large array alive.

Cheat Sheet

Operation Java Go Complexity
Length s.length() len(s) O(1)
Char Access s.charAt(i) s[i] O(1)
Substring s.substring(i, j) s[i:j] Java O(N), Go O(1)
Contains s.contains(sub) strings.Contains(s, sub) O(N*M) (usually)
Split s.split(regex) strings.Split(s, sep) O(N)
To Char/Byte Array s.toCharArray() []byte(s) O(N)

Next Steps

You’ve mastered the basics of strings. The next module will dive into Linked Lists, where we move away from contiguous memory.

Course Glossary

1. Practice in the Vault

Looking to solidify your understanding? Head over to the Problem Vault to solve curated problems related to this module with detailed walkthroughs and optimal solutions.