| description |
|---|
String problems are very similar to array problems as they both use very similar techniques but there are some slight differences |
Similar to arrayswith some differences:
- Concatenation:
$$O(m + n)$$ - Find substring:
$$O(m \times n)$$ (can be improved using Rabin Karp) - Slice:
$$O(m)$$ - Split by token:
$$O(m + n)$$ - Strip:
$$O(n)$$
- Empty strings
- Strings with 1 or 2 characters
- Strings with repeated characters
- Strings with only distinct characters
- Input character set (ASCII, UTF-8, all lowercase alphabets, etc.)
- Case sensitivity
Similar to arrayswith some additions:
- Think about using two pointers more
- Count the frequency of characters using a fingerprint frequency array over a hash table if input character set is fixed size
- Bitmasking to find duplicates
- Anagram checking using frequency over sorting
- Palindrome checking using converging two pointers
- Counting the number of palindromes using two pointers diverging from middle