Skip to content

Volume ITechnology

4.0.14 — String Rotation, Compression, Longest Common Prefix ​

Classic · Easy · LeetCode 796 (Rotate String), LeetCode 443 (String Compression), LeetCode 14 (Longest Common Prefix)

The problem ​

  1. Is one string a rotation of another? "erbottlewat" is a rotation of "waterbottle". Move "wat" from the front to the back and you get it.
  2. Compress runs of repeated characters. "aaabbc" becomes "a3b2c1".
  3. Find the longest prefix shared by a list of words. For ["flower", "flow", "flight"] it is "fl".

1. Is it a rotation? ​

What rotating means ​

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].

The slow way ​

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).

The one-line trick ​

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"))   # → True
print(is_rotation("abc", "acb"))                   # → False
print(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.

2. Compress runs ​

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"))     # → a3b2c1
print(compress("abcd"))       # → a1b1c1d1
print(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"))   # → aaabbc
print(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.

3. Longest common prefix ​

A prefix is a piece from the start of a string. "fl" and "flo" are prefixes of "flower".

Compare column by column ​

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"]))   # → fl
print(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.

The sorting trick ​

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.

Complexity ​

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.

What the interviewer will push on ​

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."

Next: 4.0.15 Largest, Smallest and Second Largest. The first array problem, and the "keep the best so far" pattern.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet