Rotating a string moves some characters from the front to the back. "waterbottle" rotated by 3 is "erbottle" + "wat". In Python, rotating left by k is s[k:] + s[:k].
Try every possible rotation of the first string and compare each with the second. There are n rotations, and each one costs n to build and compare. That is O(n^2).
Write the string twice in a row. Every rotation appears inside it.
waterbottle + waterbottle = waterbottlewaterbottle erbottlewat ← there it is
Why? Any rotation is some back part of the string followed by the front part. In s + s, every back part of the first copy runs straight into the front of the second copy. So every rotation of s sits somewhere inside s + s.
python
def is_rotation(a: str, b: str) -> bool: return len(a) == len(b) and b in a + a # (1)print(is_rotation("waterbottle", "erbottlewat")) # → Trueprint(is_rotation("abc", "acb")) # → Falseprint(is_rotation("abc", "bc")) # → False
(1) The length check is needed. Without it, "bc" would count as a rotation of "abc", since "bc" appears inside "abcabc". A rotation must use every character.
Python's in for strings is a fast search, close to O(n) in practice. So the whole check is about O(n) time and O(n) memory for the doubled string. This question is famous partly because it appears in the book Cracking the Coding Interview, with the rule that you may call a substring check only once.
Walk the string. Count how long the current run of equal characters is. When the character changes, write the character and its count, then start a new run.
python
def compress(s: str) -> str: if not s: return "" out = [] count = 1 for i in range(1, len(s)): if s[i] == s[i - 1]: # (1) count += 1 else: out.append(s[i - 1] + str(count)) # (2) count = 1 out.append(s[-1] + str(count)) # (3) return "".join(out)print(compress("aaabbc")) # → a3b2c1print(compress("abcd")) # → a1b1c1d1print(compress("zzzzzzzzzzzz")) # → z12
(1) Same as the previous character, so the run continues.
(2) The run just ended. Write the character that made it and how long it was.
(3) The last run never meets a "different" character, so the loop never writes it. Writing it after the loop is the step everyone forgets. Without it, "aaabbc" would give "a3b2".
Common follow-ups.
"Return the original if the compressed one is not shorter.""abcd" turns into "a1b1c1d1", which is twice as long. Add return min(result, s, key=len). If the two lengths tie, min keeps the first, the compressed string, so write s first if you prefer the original on a tie.
"Leave out counts of 1.""aaabbc" becomes "a3b2c". Write the count only when it is above 1. That is LeetCode 443.
"Decompress it." Read a character, then read all the digits after it, because a count can have more than one digit, like z12.
python
def decompress(s: str) -> str: out, i = [], 0 while i < len(s): ch = s[i] i += 1 num = 0 while i < len(s) and s[i].isdigit(): # read every digit of the count num = num * 10 + int(s[i]) i += 1 out.append(ch * num) return "".join(out)print(decompress("a3b2c1")) # → aaabbcprint(decompress("z12")) # → zzzzzzzzzzzz
num * 10 + int(s[i]) is Horner's method from 4.0.9, building a number one digit at a time.
This kind of compression is called run-length encoding. Fax machines used it from the 1960s onward. A faxed page is mostly long runs of white dots, so "500 white, 3 black, 200 white" is far shorter than listing every dot.
Look at position 0 of every word. If all words have the same character there, it is part of the prefix. Move to position 1. Stop at the first position where a word is too short or the characters differ.
python
def longest_common_prefix(words: list[str]) -> str: if not words: return "" first = words[0] for i in range(len(first)): # (1) ch = first[i] for w in words[1:]: if i == len(w) or w[i] != ch: # (2) return first[:i] return first # (3)print(longest_common_prefix(["flower", "flow", "flight"])) # → flprint(repr(longest_common_prefix(["dog", "racecar", "car"]))) # → ''print(longest_common_prefix(["interview", "internet", "interval"])) # → inter
(1) The prefix can never be longer than the first word, so its positions are enough to try.
(2) Stop when some word has run out of characters, or has a different one here. Check the length first. Otherwise w[i] would crash with an IndexError on a short word.
(3) The whole first word is a prefix of every other word.
Sort the words. Alphabetical order puts words with long shared prefixes next to each other. The first and last words in sorted order are the most different pair. Whatever prefix those two share, every word in between shares too. So you only need to compare two words.
python
def lcp_sorted(words: list[str]) -> str: if not words: return "" lo, hi = min(words), max(words) # (1) i = 0 while i < len(lo) and lo[i] == hi[i]: i += 1 return lo[:i]print(lcp_sorted(["flower", "flow", "flight"])) # → fl
(1) You do not even need a full sort. min and max find the first and last words in alphabetical order in one pass each.
Why is the shared prefix of the first and last words shared by all? Alphabetical order compares character by character from the left. If the first and last words both start with "fl", every word between them must also start with "fl". A word starting with anything else would sort before the first or after the last.
Rotation: about O(n) time and O(n) memory. Compression: O(n) time. Longest common prefix: O(S) time, where S is the total number of characters in all the words, because in the worst case every character is checked once. The min/max version is also O(S), with a simpler loop.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Check whether b is a rotation of a, with one search."len(a) == len(b) and b in a + a. Every rotation of a appears inside a written twice in a row. The length check stops a short piece like "bc" from passing.
"Your compression is missing the last group of letters. Why?" The loop only writes a group when the letter changes. The last group never sees a change. So write it once more after the loop ends.
"What if a count has two digits, like z12?" When decompressing, keep reading digits until you hit a letter. Build the number with num = num * 10 + digit.
"Can you find the longest common prefix faster?" You must look at the prefix characters in every word, so you cannot do much better. One shortcut: compare only the alphabetically first and last words, using min and max. For many prefix questions on the same words, a trie is the right tool (4.15).
One thing to volunteer: "Writing something twice in a row is a general trick for anything circular. It turns a wrap-around problem into a straight one."