Simplify Path

Problem

Given an absolute Unix-style file path (a string starting with /), reduce it to its canonical form:

• A single dot . means “current directory” — it disappears.
• A double dot .. means “go up one directory” — it removes the previous directory name (at the root it does nothing).
• Multiple consecutive slashes collapse into one.
• Any other run of characters between slashes — including names like ... or a..b — is a legitimate directory name and must be kept verbatim.

The canonical path must start with exactly one /, use single slashes between names, not end with a trailing slash (unless the whole path is just /), and contain no . or .. components.

Examples

Example 1

Input: path = "/home//foo/./" Output: "/home/foo" Explanation: the double slash collapses, . is dropped, and the trailing slash is removed.

Example 2

Input: path = "/a/b/../../c/" Output: "/c" Explanation: the first .. cancels b, the second cancels a, leaving only c.

Example 3

Input: path = "/../.../up" Output: "/.../up" Explanation: .. at the root is a no-op, and ... is an ordinary directory name, not a “go up twice.”

Constraints

• 1 <= path.length <= 3000
• path consists of letters, digits, ., /, and _, and begins with /.
• A single linear pass is expected — O(n) time.

Think about it first

TL;DR

Split on / and replay the components onto a stack (.. pops, names push) — O(n) time, O(n) space.

Approach 1 — Brute force (repeated textual rewriting)

Keep applying the rules directly to the string until nothing changes: collapse // to /, delete /./, and resolve the leftmost /<name>/../ by scanning back for the previous slash and cutting the segment out.

def simplifyPath(path: str) -> str:
    path += "/"
    changed = True
    while changed:
        changed = False
        if "//" in path:
            path = path.replace("//", "/")
            changed = True
        elif "/./" in path:
            path = path.replace("/./", "/")
            changed = True
        else:
            i = path.find("/../")
            if i != -1:
                j = path.rfind("/", 0, i) if i > 0 else 0
                path = path[:j] + path[i + 3 :]
                changed = True
    if len(path) > 1 and path.endswith("/"):
        path = path[:-1]
    return path if path else "/"

Complexity: each rewrite copies the whole string and there can be O(n) rewrites, so O(n²) time, O(n) space. At n = 3000 this still runs, but it is fiddly, easy to get wrong (e.g. distinguishing /../ from /.../), and quadratic. The O(n) constraint is a signal to tokenize the path instead of rewriting the string repeatedly.

Approach 2 — Split + stack

Slashes are only separators. After path.split("/"), every rule becomes a decision about one whole component, and .. means “undo the most recent kept component,” which is exactly a stack pop. Empty strings (from // and the leading /) and "." are skipped; everything else, including "...", is a name to push.

def simplifyPath(path: str) -> str:
    stack: list[str] = []
    for comp in path.split("/"):
        if comp == "" or comp == ".":
            continue
        if comp == "..":
            if stack:
                stack.pop()
        else:
            stack.append(comp)
    return "/" + "/".join(stack)

Walkthrough of Example 2 — path = "/a/b/../../c/":

split("/") → ["", "a", "b", "..", "..", "c", ""]

Result: "/" + "c" → "/c". Matches. (In Example 3, .. arrives while the stack is empty — the if stack guard makes it a no-op, and ... falls through to the push branch as a plain name.)

Complexity: O(n) time (split, one pass, join), O(n) space for the components and stack.

Variant worth knowing — manual tokenizer, no split

Interviewers sometimes ask for the same thing without str.split, to see the two-pointer scan. Same algorithm, hand-rolled tokenization:

def simplifyPath(path: str) -> str:
    stack: list[str] = []
    i, n = 0, len(path)
    while i < n:
        while i < n and path[i] == "/":
            i += 1
        j = i
        while j < n and path[j] != "/":
            j += 1
        comp = path[i:j]
        if comp == "..":
            if stack:
                stack.pop()
        elif comp and comp != ".":
            stack.append(comp)
        i = j
    return "/" + "/".join(stack)

Complexity: O(n) time, O(n) space — identical; it only trades library splitting for explicit pointers.

Common pitfalls

• Treating anything starting with dots as special: "..." and "a..b" are valid directory names — only the exact strings "." and ".." have meaning.
• Popping on ".." without checking the stack is non-empty — going above root must be a silent no-op, not an exception.
• Building the result as "/".join(stack) without the leading "/", or leaving a trailing slash; the empty-stack case must return exactly "/" (the join formula handles it: "/" + "").
• Doing replace passes on the raw string and matching ".." inside "..." — tokenize first, then compare whole components.

Pattern takeaway

When input rules include an “undo the most recent item” operation (.., backspace, canceling pair), tokenize the input and replay the tokens onto a stack: keeps push, undos pop, no-ops skip. The stack’s final contents are the canonical answer — the same skeleton handles path canonicalization, backspace-editing, and tag matching.