Skip to main content

String Cheatsheet

A string is a sequence of characters. Many tips that apply to Arrays also apply to Strings.

Time complexity​

A Strings is an array of characters, so the time complexities of basic string operations will closely resemble that of array operations.

Operation Big-O
Access O(1)
Search O(n)
Insert O(n)
Remove O(n)

Operations involving another String​

Here we assume the other string is of length m.

Operation Big-O
Find substring O(n.m)
Concatenating strings O(n + m)
Slice O(m)
Split (by token) O(n + m)
Strip (remove leading and trailing whitespaces) O(n)

Things to look out for during interviews​

  • Ask about 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

Techniques​

Many string questions fall into one of these buckets.

Counting characters​

Often you will need to count the frequency of characters in a string. The most common way of doing that is by using a hash table/map in your language of choice. 

If you need to keep a counter of characters, a common mistake is to say that the space complexity required for the counter is O(n). The space required for a counter of a string of latin characters is O(1) not O(n). This is because the upper bound is the range of characters, which is usually a fixed constant of 26. The input set is just lowercase Latin characters.

String of unique characters​

A neat trick to count the characters in a string of unique characters is to use a 26-bit bitmask to indicate which lower case latin characters are inside the string.

mask = 0
for c in word:
  mask |= (1 << (ord(c) - ord('a')))

To determine if two strings have common characters, perform & on the two bitmasks. If the result is non-zero, ie. mask_a & mask_b > 0, then the two strings have common characters.

Palindrome​

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as madam or racecar.

Here are ways to determine if a string is a palindrome:

  • Reverse the string and it should be equal to itself.
  • Have two pointers at the start and end of the string. Move the pointers inward till they meet. At every point in time, the characters at both pointers should match.

The order of characters within the string matters, so hash tables are usually not helpful.

When a question is about counting the number of palindromes, a common trick is to have two pointers that move outward, away from the middle.

  • Note that palindromes can be even or odd length. For each middle pivot position, you need to check it twice - once that includes the character and once without the character. 
  • For substrings, you can terminate early once there is no match


Back to top