Interview Cheat Sheets | Strings Cheat Sheet

Introduction

This article will serve to further summarize the excellent overview of handling strings from the tech interview handbook.

A string is an array of characters, and many concepts applicable to arrays also apply to strings.
Common data structures for looking up strings include Trie/Prefix Tree and Suffix Tree.
Common string algorithms include Rabin Karp for substring searching and KMP for efficient substring searching.

Operation	Big-O	Note
Find substring	O(n.m)	Naive case. More efficient algorithms like KMP exist
Concatenating strings	O(n + m)
Slice	O(m)
Split (by token)	O(n + m)
Strip (remove whitespace)	O(n)	Remove leading and trailing whitespaces

Consider input character set and case sensitivity.
Corner cases: Empty string, string with 1 or 2 characters, string with repeated characters, strings with only distinct characters.

Counting characters:
- Use a hash table/map for character frequency.
- Space complexity for a counter of Latin characters is O(1), not O(n).
A string of unique characters:
- Use a 26-bit bitmask to indicate characters inside the string.
Anagram:
- Sorting both strings.
- Mapping characters to prime numbers.
- Frequency counting of characters.
Palindrome:
- Reverse the string and compare the two strings to each other, or use two pointers.
- For counting palindromes, move pointers outward, considering even and odd lengths.
- For finding the longest palindrome of a string, consider instantiating an array of a length that can contain the problem string subspace, and using that array in place to store counts of each character in the string.