324. Longest Safe Path in a String

Longest Safe Path in a String

You are given a string containing lowercase English letters and # characters. Each # is a blocker that normally cannot be included in a safe path.

A safe path is a continuous substring containing only lowercase English letters. Find the longest safe path in the given string.

As a follow-up, also find the longest continuous substring when at most one # may be treated as safe and included in the path.

Both methods must be implemented in the same class: SafePathFinder.

Method Signatures

Longest Path Without a Blocker

String longestSafePath(String path)

Returns the longest continuous substring that contains only lowercase English letters.
The returned substring must not contain #.
If multiple longest substrings exist, return the one that starts at the smallest index.
If the string contains no lowercase letters, return an empty string.

Longest Path Allowing One Blocker

String longestSafePathWithOneHash(String path)

Returns the longest continuous substring containing at most one #.
The allowed # remains part of the returned substring.
The substring may contain zero or one #, but never more than one.
If multiple longest substrings exist, return the one that starts at the smallest index.

Constraints

1 ≤ path.length() ≤ 100,000
path contains only lowercase English letters and # characters.
path is never empty or null.

Examples

Example 1: No Blocker Allowed

Method call: longestSafePath(path = "xy#mnop##rst")

Output: "mnop"

The letter-only segments are "xy", "mnop", and "rst". The longest one is "mnop".

Example 2: One Blocker Allowed

Method call: longestSafePathWithOneHash(path = "go##river#bridge")

Output: "river#bridge"

The returned substring connects "river" and "bridge" by treating the single blocker between them as safe.

Example 3: Equal-Length Paths

Method call: longestSafePath(path = "abc#def#ghi")

Output: "abc"

All three safe paths have the same length, so the path beginning at the smallest index is returned.

Example 4: Only Blockers

Method call: longestSafePath(path = "####")

Output: ""

There are no lowercase letters, so no safe path exists.

Example 5: One Blocker Among Letter Segments

Method call: longestSafePathWithOneHash(path = "ab##cde#fghij")

Output: "cde#fghij"

The letter-only segment lengths are 2,0,3,5. Allowing one blocker connects the adjacent segments of lengths 3 and 5, producing the longest valid substring.