DSA-048 · Lexical Unix component stack

Simplify Absolute Path

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21540 deterministic checks. Learner drafts are not executed.

Understand the problem

Normalize an absolute Unix-style path lexically by collapsing separators, current-directory components, and parent traversals at root.

path is non-null with 1–100,000 UTF-16 code units, begins with /, and contains no NUL. Both methods throw IllegalArgumentException for empty, relative, or NUL-containing input. Slash is the only separator.
Ignore empty components and exactly .; exactly .. removes the last retained component if one exists and otherwise stays at root. Every other component, including ..., percent-encoded text, whitespace, backslashes, and non-ASCII names, is an ordinary literal name.
Return one leading slash, single separators between retained names, and no trailing slash unless the result is root /. Do not read the filesystem, follow symbolic links, decode percent escapes, normalize Unicode, or establish filesystem authorization/security. Preserve the immutable input.

Examples

Input: "/a//b/../c/./"
Output: "/a/c"
Ignore empty/dot components and cancel b with its following parent traversal.
Input: "/../../.../x"
Output: "/.../x"
Root parents stay at root; ... is a literal directory name.

Before you start

Stack top versus bottom and last-in-first-out order
Loop invariants, checked arithmetic, and amortized analysis

Recognize the structure

Each completed component acts on the current canonical directory sequence. A literal name appends one level; a parent traversal removes the most recent retained level, making a stack the natural state.

Try before revealing

Hint 1

What does one parent component undo in the processed path?

Hint 2

Which names are special only by exact equality?

Hint 3

Build canonical components, clamp parents at root, and join once.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Split into tokens, then normalize

Split with a retained-empty policy, examine each component, and keep a list of names. For /a//b/../, tokens are empty,a,empty,b,..,empty; normalization retains only a and returns /a. This O(L) baseline is already asymptotically optimal, but allocates the full token array. The manual scan demonstrates component boundaries without that up-front array.

Improve the baseline

Find complete components

Scan from after the leading slash until each slash or the end boundary. The end boundary finalizes a last component without reading path[length].

Apply component semantics

For .., remove the last retained name only when one exists. Ignore empty and . components. Append every other component literally.

Join one canonical path

Join retained names with one slash and prepend the root slash. An empty component stack produces / automatically, with no trailing separator for non-root results.

Why it is correct

Canonical-prefix invariant

After each complete component, the deque in root-to-leaf order contains exactly the normalized names for the processed absolute prefix. Leading and repeated slashes contribute empty components and therefore no names.

Transition preservation

An ordinary name appends a directory level, dot leaves the state unchanged, and parent removes the latest level or remains at root when none exists. These operations exactly implement the lexical contract, including literal multi-dot names.

Output and scope

Joining the final names yields one leading slash and no redundant separators or special dot components. Each input code unit is scanned once. The proof is lexical only: symbolic-link targets and real filesystem permissions can change the meaning of a path and are not observed here.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(String path) {
        if (path.isEmpty() || path.charAt(0) != '/' || path.indexOf(0) >= 0) throw new IllegalArgumentException("absolute path without NUL required");
    }
    public static String simplifyPath(String path) {
        validate(path);
        ArrayDeque<String> components = new ArrayDeque<>();
        int start = 1;
        for (int i = 1; i <= path.length(); i++) {
            if (i == path.length() || path.charAt(i) == '/') {
                String part = path.substring(start, i);
                if (part.equals("..")) { if (!components.isEmpty()) components.removeLast(); }
                else if (!part.isEmpty() && !part.equals(".")) components.addLast(part);
                start = i + 1;
            }
        }
        return "/" + String.join("/", components);
    }
    public static String baseline(String path) {
        validate(path);
        List<String> components = new ArrayList<>();
        for (String part : path.split("/", -1)) {
            if (part.equals("..")) { if (!components.isEmpty()) components.removeLast(); }
            else if (!part.isEmpty() && !part.equals(".")) components.add(part);
        }
        return "/" + String.join("/", components);
    }
}

Read the meaningful blocks

Short-circuit the end boundary

i==path.length() is tested before charAt(i), so no out-of-range access is needed to flush the final component.

Compare full component strings

Only exactly .. is a parent operation; startsWith("..") would destroy legitimate names such as ... or ..cache.

Keep root-to-leaf deque order

addLast/removeLast treats the end as the stack top while String.join iterates the canonical path order directly.

Complexity

O(L) time and O(L) workspace/output for input length L, including retained component strings and the final path. The manual parser avoids a full split token array but is not a constant-space algorithm.

The split-based baseline also uses O(L) time and O(L) storage, with additional token-array and empty-token overhead. This is an allocation/mechanism comparison, not an asymptotic time improvement.

Exact-state walkthroughs

Reveal normal and boundary traces

Canonical components survive only meaningful operations

Input: "/a//b/../c/./" · Result: "/a/c"

Step 1 of 9: Begin at root with no retained names.

Components are displayed root to leaf; only exact . and .. names are special.

Original text positions

0: "/"
1: "a"
2: "/"
3: "/"
4: "b"
5: "/"
6: "."
7: "."
8: "/"
9: "c"
10: "/"
11: "."
12: "/"

Canonical names — root to leaf, top at leaf

Empty at this step.

State after this step
Variable	Value
text	`"/a//b/../c/./"`
components	`[]`
start	`1`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(String path) {
 4         if (path.isEmpty() || path.charAt(0) != '/' || path.indexOf(0) >= 0) throw new IllegalArgumentException("absolute path without NUL required");
 5     }
 6     public static String simplifyPath(String path) {
 7         validate(path);
 8         ArrayDeque<String> components = new ArrayDeque<>();
 9         int start = 1;
10         for (int i = 1; i <= path.length(); i++) {
11             if (i == path.length() || path.charAt(i) == '/') {
12                 String part = path.substring(start, i);
13                 if (part.equals("..")) { if (!components.isEmpty()) components.removeLast(); }
14                 else if (!part.isEmpty() && !part.equals(".")) components.addLast(part);
15                 start = i + 1;
16             }
17         }
18         return "/" + String.join("/", components);
19     }
20     public static String baseline(String path) {
21         validate(path);
22         List<String> components = new ArrayList<>();
23         for (String part : path.split("/", -1)) {
24             if (part.equals("..")) { if (!components.isEmpty()) components.removeLast(); }
25             else if (!part.isEmpty() && !part.equals(".")) components.add(part);
26         }
27         return "/" + String.join("/", components);
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin at root with no retained names.
Components are displayed root to leaf; only exact . and .. names are special.
text
"/a//b/../c/./"
components
[]
start
1
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
1
end
2
part
"a"
start
3
components
["a"]
canonicalPrefix
"/a"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
3
end
3
part
""
start
4
components
["a"]
canonicalPrefix
"/a"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
4
end
5
part
"b"
start
6
components
["a","b"]
canonicalPrefix
"/a/b"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
6
end
8
part
".."
start
9
components
["a"]
canonicalPrefix
"/a"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
9
end
10
part
"c"
start
11
components
["a","c"]
canonicalPrefix
"/a/c"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
11
end
12
part
"."
start
13
components
["a","c"]
canonicalPrefix
"/a/c"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/a//b/../c/./"
oldStart
13
end
13
part
""
start
14
components
["a","c"]
canonicalPrefix
"/a/c"
Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
result
"/a/c"

Parent traversal is clamped at root

Input: "/../../.../x" · Result: "/.../x"

Step 1 of 6: Begin at root with no retained names.

Components are displayed root to leaf; only exact . and .. names are special.

Original text positions

0: "/"
1: "."
2: "."
3: "/"
4: "."
5: "."
6: "/"
7: "."
8: "."
9: "."
10: "/"
11: "x"

Canonical names — root to leaf, top at leaf

Empty at this step.

State after this step
Variable	Value
text	`"/../../.../x"`
components	`[]`
start	`1`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(String path) {
 4         if (path.isEmpty() || path.charAt(0) != '/' || path.indexOf(0) >= 0) throw new IllegalArgumentException("absolute path without NUL required");
 5     }
 6     public static String simplifyPath(String path) {
 7         validate(path);
 8         ArrayDeque<String> components = new ArrayDeque<>();
 9         int start = 1;
10         for (int i = 1; i <= path.length(); i++) {
11             if (i == path.length() || path.charAt(i) == '/') {
12                 String part = path.substring(start, i);
13                 if (part.equals("..")) { if (!components.isEmpty()) components.removeLast(); }
14                 else if (!part.isEmpty() && !part.equals(".")) components.addLast(part);
15                 start = i + 1;
16             }
17         }
18         return "/" + String.join("/", components);
19     }
20     public static String baseline(String path) {
21         validate(path);
22         List<String> components = new ArrayList<>();
23         for (String part : path.split("/", -1)) {
24             if (part.equals("..")) { if (!components.isEmpty()) components.removeLast(); }
25             else if (!part.isEmpty() && !part.equals(".")) components.add(part);
26         }
27         return "/" + String.join("/", components);
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin at root with no retained names.
Components are displayed root to leaf; only exact . and .. names are special.
text
"/../../.../x"
components
[]
start
1
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/../../.../x"
oldStart
1
end
3
part
".."
start
4
components
[]
canonicalPrefix
"/"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/../../.../x"
oldStart
4
end
6
part
".."
start
7
components
[]
canonicalPrefix
"/"
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/../../.../x"
oldStart
7
end
10
part
"..."
start
11
components
["..."]
canonicalPrefix
"/..."
Normalize one complete component lexically.
Literal names append, parent removes one retained level or stays at root, and dot/empty components change nothing. No filesystem is consulted.
text
"/../../.../x"
oldStart
11
end
12
part
"x"
start
13
components
["...","x"]
canonicalPrefix
"/.../x"
Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
result
"/.../x"

Test the contract

Input: "/"
Output: "/"
Root stays root.
Input: "/a//b/../c/./"
Output: "/a/c"
Repeated separators and dot operations.
Input: "/../../..."
Output: "/..."
Root clamp and literal multi-dot name.
Input: "a/b"
Output: IllegalArgumentException
Relative input is outside this API.

Common mistakes and counterexamples

Treat every multi-dot name as a parent

Counterexample: /.../x must keep the ... name.

Match exactly .. and . only.

Pop above root

Counterexample: /../../ normalizes to / without an empty-stack failure.

Check whether a retained name exists before removing it.

Claim lexical normalization resolves symlinks or access

Counterexample: /link/../secret may have different real filesystem meaning if link is a symbolic link.

Keep this a pure string normalization API; filesystem resolution and authorization need separate trusted operations.

Follow-ups

Normalize relative paths.

Leading .. components may need to remain instead of being clamped at root. Define the base directory and whether the result stays relative before reusing the absolute-path transitions.

Resolve symbolic links.

Real resolution requires filesystem access, existence/error policy, and a clear trust boundary. Lexically simplifying before resolution can change semantics; a string stack alone cannot implement realpath behavior.

Process streamed chunks.

Retain an unfinished component across chunk boundaries and apply transitions only when a separator or end arrives. Splitting each chunk independently would mishandle names and .. components spanning chunks.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 139/20,000 characters

Self-review

I preserve literal names and root semantics.I flush the final component without an invalid read.I distinguish lexical normalization from filesystem resolution.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Stacks: pending work, saved state, and monotonic spans

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.