Count letters whose lowercase copies all come before uppercase: Frontier Interview's solution

Question: Count letters whose lowercase copies all come before uppercase

Companies: Microsoft

Difficulty: Medium

Problem statement

Given a string s of English letters (it may also contain other characters, which you ignore), count the distinct letters, compared case-insensitively, that satisfy this rule:

Every lowercase occurrence of the letter appears before every uppercase occurrence of the same letter.

A letter that appears only in lowercase, or only in uppercase, satisfies the rule.

Implement:

def count_ordered_letters(s: str) -> int: ...

Constraints

0 <= len(s) <= 10^5
Aim for O(n) time.

Example 1

Input:  s = "xxXyYyz"
Output: 2

x: both lowercase copies come before X, so it counts. y: a lowercase y follows Y, so it does not. z: lowercase only, so it counts.

Example 2

Input:  s = "Hello hELLO"
Output: 3

e, l and o count. h does not, because a lowercase h follows H.

Approach

For each letter (compared case-insensitively) we ask one question: does any
lowercase copy show up after an uppercase copy? If never, the letter counts.
A letter seen in only one case counts automatically, because there is no
uppercase copy for a lowercase one to follow (or no lowercase copy at all).

Brute force. For each of the 26 letters, collect the positions of its
lowercase and uppercase copies, then check every lowercase position against
every uppercase position. That is O(n²) per letter in the worst case. A quick
improvement is to compare only two numbers per letter: the last lowercase
index must be smaller than the first uppercase index. Two passes (or one
pass that records both indices) give O(n).

Optimal, single pass. Scan left to right and keep three small tables
indexed by letter:

seen[c]: the letter has appeared in either case.
upper_seen[c]: an uppercase copy has appeared so far.
broken[c]: a lowercase copy appeared after an uppercase copy.

When we read a lowercase letter and upper_seen is already set, the letter is
broken for good. The answer is the number of letters that are seen and not
broken.

Invariant: after processing a prefix, broken[c] is true exactly when that
prefix contains an uppercase C followed later by a lowercase c. A letter's
status can only move from "good" to "broken", never back, which is also why the
same scan works on a stream.

Non-letters (digits, spaces) are ignored; clarify this with the interviewer.

Code

from typing import Iterable


def count_ordered_letters(s: str) -> int:
    """Count distinct letters (case-insensitive) whose lowercase copies
    all appear before any uppercase copy. Single-case letters count."""
    seen = [False] * 26
    upper_seen = [False] * 26
    broken = [False] * 26

    for ch in s:
        if "a" <= ch <= "z":
            i = ord(ch) - ord("a")
            seen[i] = True
            if upper_seen[i]:
                broken[i] = True
        elif "A" <= ch <= "Z":
            i = ord(ch) - ord("A")
            seen[i] = True
            upper_seen[i] = True
        # anything else is ignored

    return sum(1 for i in range(26) if seen[i] and not broken[i])


def count_ordered_letters_indices(s: str) -> int:
    """Two-index version: last lowercase index < first uppercase index."""
    last_lower = [-1] * 26
    first_upper = [-1] * 26
    for idx, ch in enumerate(s):
        if "a" <= ch <= "z":
            last_lower[ord(ch) - 97] = idx
        elif "A" <= ch <= "Z":
            i = ord(ch) - 65
            if first_upper[i] == -1:
                first_upper[i] = idx
    count = 0
    for i in range(26):
        lo, up = last_lower[i], first_upper[i]
        if lo == -1 and up == -1:
            continue
        if lo == -1 or up == -1 or lo < up:
            count += 1
    return count


class OrderedLetterCounter:
    """Streaming version: feed characters, ask for the count at any time."""

    def __init__(self) -> None:
        self.seen = [False] * 26
        self.upper_seen = [False] * 26
        self.broken = [False] * 26
        self.good = 0  # letters seen and not broken

    def feed(self, chunk: Iterable[str]) -> None:
        for ch in chunk:
            if not ch.isascii() or not ch.isalpha():
                continue
            i = ord(ch.lower()) - 97
            if not self.seen[i]:
                self.seen[i] = True
                self.good += 1
            if ch.isupper():
                self.upper_seen[i] = True
            elif self.upper_seen[i] and not self.broken[i]:
                self.broken[i] = True
                self.good -= 1

    def count(self) -> int:
        return self.good


if __name__ == "__main__":
    cases = {
        "": 0,
        "abc": 3,
        "ABC": 3,
        "aA": 1,
        "Aa": 0,
        "aAa": 0,
        "xxXyYyz": 2,
        "Hello hELLO": 3,
        "bBbB": 0,
        "a1A!": 1,
    }
    for text, want in cases.items():
        assert count_ordered_letters(text) == want, (text, want)
        assert count_ordered_letters_indices(text) == want, (text, want)
        c = OrderedLetterCounter()
        c.feed(text)
        assert c.count() == want, (text, want)
    print("ok")

Complexity

count_ordered_letters: O(n) time for a string of length n, O(1) extra
space (three tables of 26 flags).
count_ordered_letters_indices: O(n) time, O(1) space.
OrderedLetterCounter.feed: O(k) for a chunk of k characters; count is
O(1) because the running total is kept up to date. Space O(1).

Test cases

"" → 0 (no letters).
"abc" → 3 (lowercase only, all count).
"ABC" → 3 (uppercase only, all count).
"aA" → 1 (lowercase strictly before uppercase).
"Aa" → 0 (a lowercase copy follows the uppercase one).
"aAa" → 0 (one late lowercase copy is enough to break it).
"xxXyYyz" → 2 (x and z count; y has a lowercase after Y).
"Hello hELLO" → 3 (e, l, o count; h breaks because
lowercase h follows H).
"bBbB" → 0.
"a1A!" → 1 (non-letters ignored).
"zZzZ" * 50_000 → 0 (large input, still one pass).
"abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ" → 26.

Follow-ups

Letter must appear in both cases. Some versions only count a letter if
it appears in lowercase and uppercase. Add lower_seen and require
lower_seen and upper_seen and not broken. One extra table, same O(n).
Return the letters, not the count. Collect chr(97 + i) for good
letters in alphabetical order. Same complexity.
Streaming input or a huge file. The state is 26 flags plus a running
count, so read in chunks and keep OrderedLetterCounter between them. A
letter never goes from broken back to good, so the running count only
moves down on a break and up on a first sighting.
Queries over substrings s[l:r]. For each letter precompute sorted
lists of lowercase and uppercase positions. For a query, find the last
lowercase position < r and the first uppercase position >= l with
binary search, and check that one is missing or the lowercase is earlier.
O(26 log n) per query after O(n) preprocessing.
Unicode letters. Replace the 26-slot arrays with dictionaries keyed by
ch.casefold(), and use str.islower / str.isupper. Note that some
characters have no case and some case mappings are not one-to-one.

Interviewer expectations

Mid-level (L4)

Restates the rule, including that single-case letters count, and asks how
to treat non-letters.
Reaches an O(n) solution, either one pass with flags or last-lowercase vs
first-uppercase indices.
Tests "Aa", "aA", an empty string and a single-case string.

Senior (L5)

Explains the invariant (a letter can only go from good to broken) and uses
it to justify a single pass and O(1) space.
Handles the "both cases required" variant without rewriting the solution.
Writes compact, readable code with no off-by-one in index comparisons.

Staff (L6+)

Turns the scan into a streaming counter with an O(1) running count.
Discusses range queries with per-letter position lists and binary search.
Raises Unicode case folding and its edge cases, and states what the
function promises for them.