DSA · Chapter 9 of 40
Strings
Strings are sequences of characters. In most languages they are immutable, so every concatenation creates a new string — building a big string in a loop should use a list and join at the end.
String questions usually reduce to array techniques: counting characters, two pointers, or sliding windows.
Immutability
s += ch inside a loop is O(n^2) because each step copies the whole string. Collect parts in a list and join once for O(n).
Character counting
A dictionary or a fixed array of size 26 is enough for anagram and frequency problems.
Example 1 (python)
parts = []
for ch in 'dsa':
parts.append(ch.upper())
print(''.join(parts))Output
DSAJoining once avoids repeated copying.
Example 2 (python)
def is_anagram(a, b):
if len(a) != len(b):
return False
counts = {}
for ch in a:
counts[ch] = counts.get(ch, 0) + 1
for ch in b:
if counts.get(ch, 0) == 0:
return False
counts[ch] -= 1
return True
print(is_anagram('listen', 'silent'))Output
TrueCounting characters solves anagrams in O(n).
Key points
- Strings are usually immutable.
- Build strings with a list plus join, not repeated concatenation.
- Character counts solve anagram and frequency problems.
- Most string patterns mirror array patterns.
💡 Note: Clarify whether comparisons are case-sensitive and whether spaces count.