# Strings — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/strings

> An array of characters — often immutable, which changes how you build them.

## Immutability matters

In Python, Java, and JS a string can't be changed in place. `s += c` in a loop builds a brand-new string each time — `O(n^2)` overall. Collect chars in a list/`StringBuilder` and join once.

## Build efficiently

The list-and-join pattern is linear.

```python
# slow: O(n^2)
out = ""
for ch in text:
    out += ch.upper()

# fast: O(n)
parts = []
for ch in text:
    parts.append(ch.upper())
out = "".join(parts)
```

## Common toolkit

Frequency counts (hash map / array of 26), two pointers for palindromes, sliding window for substrings, and sorting characters as an anagram key.

**Quiz:** Fastest way to test if two strings are anagrams?

- [ ] Try every permutation
- [x] Compare character counts
- [ ] Reverse one and compare

*Answer:* Compare character counts. Counting each character is O(n); permutations are O(n!).