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 characterscharacter

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.

Back to top