> For the complete documentation index, see [llms.txt](https://ashef.gitbook.io/cse201/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ashef.gitbook.io/cse201/cse201/data-structures/string.md).

# String

String Cheat Sheet

Strings, sequences of characters, share many similarities with arrays, making an understanding of arrays beneficial before exploring strings. They are pivotal in coding interviews, where a deep comprehension of string manipulation and analysis can distinguish a candidate.

### Common Data Structures for Strings

* **Trie/Prefix Tree**: Optimizes word or prefix lookups, facilitating operations like autocomplete.
* **Suffix Tree**: Supports complex string manipulations and efficient pattern searches, crucial for substring identification and analysis.

### Common String Algorithms

* **Rabin Karp**: Employs a rolling hash for efficient substring searches, ideal for plagiarism detection.
* **KMP (Knuth-Morris-Pratt)**: Eliminates backtracking in substring searches, enhancing efficiency in pattern matching.

### Time Complexity of String Operations

* **Access**: O(1), direct index access in most languages.
* **Search**: O(n), varies based on the algorithm for specific patterns.
* **Insert**: O(n), considering potential reallocation and shifting.
* **Remove**: O(n), due to shifting elements in the string.

### Operations Involving Another String

* **Find Substring**: O(n\*m) for the naive approach, with n and m being the lengths of the strings involved.
* **Concatenate**: O(n + m), combining two strings.
* **Slice**: O(m), extracting a substring.
* **Split**: O(n + m), dividing a string based on a delimiter.
* **Strip**: O(n), removing leading and trailing whitespaces.

### Considerations

* **Character Set and Sensitivity**: Clarify if the problem is case-sensitive and the allowed character set, as this can affect the solution approach.
* **Corner Cases**: Prepare for scenarios like empty strings, strings with a single character, and strings with repeated or unique characters.

### Techniques for String Problems

* **Counting Characters**: Utilize a hash table for frequency counting, an O(1) space complexity due to the fixed number of characters.
* **Unique Characters**: Implement a 26-bit bitmask for tracking unique characters, efficient for problems involving lowercase Latin characters.
* **Anagrams**: Determine anagrams through sorting, prime factor decomposition, or frequency counting, each method providing a different efficiency.
* **Palindromes**: Identify palindromes by reversing the string or using two pointers,. Char sequence is important here, not count.

### **Practice Problems**

<table><thead><tr><th width="256">Leetcode</th><th width="245">Pattern Names</th><th>Difficulty</th></tr></thead><tbody><tr><td><a href="https://leetcode.com/problems/first-unique-character-in-a-string/">First Unique Character in a String</a></td><td>Counting Characters, Unique Characters</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/valid-anagram/">Valid Anagram</a></td><td>Anagrams</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/valid-palindrome/">Valid Palindrome</a></td><td>Palindromes</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/palindrome-permutation/">Palindrome Permutation</a></td><td>Palindromes, Anagrams</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/ransom-note/">Ransom Note</a></td><td>Counting Characters</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/implement-strstr/">Implement strStr()</a></td><td>KMP</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/longest-palindrome/">Longest Palindrome</a></td><td>Palindromes, Counting Characters</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/detect-capital/">Detect Capital</a></td><td>Unique Characters</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/reverse-string/">Reverse String</a></td><td>Palindromes</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/repeated-substring-pattern/">Repeated Substring Pattern</a></td><td>KMP</td><td>Easy</td></tr><tr><td><a href="https://leetcode.com/problems/group-anagrams/">Group Anagrams</a></td><td>Anagrams</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/longest-substring-without-repeating-characters/">Longest Substring Without Repeating Characters</a></td><td>Unique Characters</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/find-all-anagrams-in-a-string/">Find All Anagrams in a String</a></td><td>Anagrams, Rabin Karp</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/longest-palindromic-substring/">Longest Palindromic Substring</a></td><td>Palindromes</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/palindrome-pairs/">Palindrome Pairs</a></td><td>Palindromes</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/minimum-window-substring/">Minimum Window Substring</a></td><td>Counting Characters</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/substring-with-concatenation-of-all-words/">Substring with Concatenation of All Words</a></td><td>Counting Characters</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/partition-labels/">Partition Labels</a></td><td>Unique Characters</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/permutation-in-string/">Permutation in String</a></td><td>Anagrams</td><td>Medium</td></tr><tr><td><a href="https://leetcode.com/problems/longest-repeating-character-replacement/">Longest Repeating Character Replacement</a></td><td>Counting Characters</td><td>Medium</td></tr></tbody></table>

### Additional Topics&#x20;

* **String Compression and Decompression**: Understanding algorithms for efficiently encoding and decoding strings.
* **Regular Expressions**: Leveraging regex for pattern matching and string manipulation tasks.
* **Dynamic Programming on Strings**: Solving problems like edit distance and substring matching through dynamic programming.