0817EasyHash TableStringDivide and ConquerBit ManipulationSliding Window

Longest Matched-Case Run

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A proofreading tool reads one line of English letters, given as line. Upper and lower case both appear and the two cases of a letter are treated as different characters.

A contiguous stretch of the line is matched when, for every letter that occurs in that stretch, the stretch contains that letter in lowercase form and also in uppercase form. For example, a stretch holding d, D and nothing else is matched, while a stretch holding d alone is not.

Return the longest matched stretch of line. If several matched stretches share the greatest length, return the one that begins at the smallest index. If the line has no matched stretch at all, return the empty string.

Examples

Example 1

Input: line = "pQqPz"
Output: "pQqP"

The stretch `pQqP` covering indices 0 through 3 uses the letters p and q, and it holds both `p` and `P` as well as both `q` and `Q`, so it is matched and 4 characters long.

Example 2

Input: line = "aAwwbBcC"
Output: "bBcC"

The stretch `bBcC` covering indices 4 through 7 uses the letters b and c, each present in both cases, so it is matched with a length of 4.

Example 3

Input: line = "nnn"
Output: ""

The only letter anywhere in the line is n and it never appears in uppercase, so no stretch is matched and the answer is the empty string.

Constraints

1 <= line.length <= 100
line consists of uppercase and lowercase English letters only.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_matched_run(line: str) -> str:

Java

public String longestMatchedRun(String line)

The intended approach

Time O(n^2) in the worst case for a line of n letters, since a piece is rescanned after each split.Space O(n) for the stack of pending pieces, beyond the returned stretch.

Work on pieces of the line, held on an explicit stack and starting with the whole line. For a piece, collect the distinct characters it holds and pick out those whose opposite case is absent from the piece. If there are none the piece is matched, so compare its width against the best found so far, breaking a tie on the smaller starting index. Otherwise every position holding one of those characters splits the piece, and the fragments between them are pushed back onto the stack.

Pythonentry point: longest_matched_run

def longest_matched_run(line):
    # A letter that appears in only one case inside a stretch can never belong to
    # a matched stretch, so every such letter cuts the piece being examined into
    # smaller pieces that are queued and examined on their own. An explicit stack
    # holds the pieces so the depth of the splitting never touches the call stack.
    # Time: O(n^2) in the worst case for a line of n letters, since each piece is
    # rescanned after a split.
    # Space: O(n) for the stack of pending pieces.
    n = len(line)
    best_start, best_len = 0, 0
    stack = [(0, n)]
    while stack:
        lo, hi = stack.pop()
        if hi <= lo:
            continue
        seen = set(line[lo:hi])
        unpaired = {c for c in seen if c.swapcase() not in seen}
        if not unpaired:
            width = hi - lo
            if width > best_len or (width == best_len and lo < best_start):
                best_start, best_len = lo, width
            continue
        piece = lo
        for i in range(lo, hi):
            if line[i] in unpaired:
                stack.append((piece, i))
                piece = i + 1
        stack.append((piece, hi))
    return line[best_start:best_start + best_len]

The obvious version

Walk over every start and every end, build the set of characters in that stretch and test the rule on it directly, keeping the widest stretch seen. Starts are visited in increasing order and a stretch replaces the incumbent only when it is strictly wider, so the earliest start wins a tie.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_matched_run(line):
    """Every stretch of the line, tested against the rule one stretch at a time."""
    n = len(line)
    best = ""
    for i in range(n):
        for j in range(i + 1, n + 1):
            seg = line[i:j]
            chars = set(seg)
            ok = True
            for c in chars:
                if c.swapcase() not in chars:
                    ok = False
                    break
            if ok and j - i > len(best):
                best = seg
    return best

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in