How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Patreon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Patreon during technical interviews.

Evaluate word-guess feedback with repeats

Q: Evaluate word-guess feedback with repeats

This question evaluates string manipulation, multiset/frequency tracking, and stateful validation across rounds, with particular emphasis on handling repeated letters and multiplicity constraints in feedback generation.

Company: Patreon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are implementing feedback for a Wordle-like guessing game. ## Part 1 — Produce feedback for one guess You are given two strings of equal length `guess` and `target` (lowercase letters). For each index `i`, output a status character: - `G` (green): `guess[i] == target[i]` - `Y` (yellow): `guess[i] != target[i]`, and the letter `guess[i]` occurs in `target` in some position **not already matched by a `G`**, respecting multiplicity (i.e., each occurrence in `target` can be used at most once across all `Y` assignments). - `W` (white/gray): otherwise. Return a string of length `n` over `{G,Y,W}`. ### Examples - `guess = "cable"`, `target = "maple"` → `WGWGG` - `guess = "paple"`, `target = "maple"` → `WGGGG` - `guess = "apple"`, `target = "maple"` → `YWGGG` ## Part 2 — Validate future guesses using past information Now the same `target` is used for multiple rounds. After each evaluated guess, you “learn” some letters are impossible. A future `guess` is considered **invalid_input** if it contains any letter that was previously confirmed to be absent from `target`. Clarification for repeated letters: a letter should be considered “confirmed absent” only if, in some previous round, **all** occurrences of that letter in that guess were marked `W` (i.e., the letter never appeared as `G` or `Y` in that round). ### Example Round 1: `guess = "cable"`, `target = "maple"` → `WGWGG` - Letters confirmed absent: `c`, `b`. Round 2: `guess = "cazle"`, `target = "maple"` → return `invalid_input` (contains `c`, which was confirmed absent). Implement the evaluator for Part 1 and the validator logic for Part 2. ## Constraints (reasonable assumptions) - `1 <= n <= 10^5` (design an efficient solution) - `guess.length == target.length` - Strings contain only lowercase English letters.

Quick Answer: This question evaluates string manipulation, multiset/frequency tracking, and stateful validation across rounds, with particular emphasis on handling repeated letters and multiplicity constraints in feedback generation.

Part 1: Produce feedback for one guess

Given two equal-length lowercase strings `guess` and `target`, return a feedback string of the same length. For each position: use `G` if the letters are equal, use `Y` if the guessed letter appears in some other unmatched position of `target`, and use `W` otherwise. Exact matches must be assigned first, and each occurrence in `target` can be used at most once across all `Y` assignments.

Constraints

1 <= len(guess) == len(target) <= 100000
Both strings contain only lowercase English letters.

Examples

Input: ('cable', 'maple')

Expected Output: 'WGWGG'

Explanation: `a`, `l`, and `e` are exact matches. The remaining target letters are `m` and `p`, so `c` and `b` are both `W`.

Input: ('apple', 'maple')

Expected Output: 'YWGGG'

Explanation: After reserving the green `p`, `l`, and `e`, only one `a` remains available for yellow. The first `a` is `Y`, but the extra `p` becomes `W`.

Input: ('aaaa', 'abca')

Expected Output: 'GWWG'

Explanation: The `a` at positions 0 and 3 are green. The two middle `a` characters cannot be yellow because all `a` occurrences in target are already used.

Input: ('bca', 'cab')

Expected Output: 'YYY'

Explanation: No letters are in the correct position, but each guessed letter appears elsewhere in the target.

Input: ('a', 'b')

Expected Output: 'W'

Explanation: Single-character edge case: the letter does not appear in the target.

Solution

def solution(guess, target):
    n = len(guess)
    counts = [0] * 26
    result = ['W'] * n

    for i in range(n):
        if guess[i] == target[i]:
            result[i] = 'G'
        else:
            counts[ord(target[i]) - 97] += 1

    for i in range(n):
        if result[i] == 'G':
            continue
        idx = ord(guess[i]) - 97
        if counts[idx] > 0:
            result[i] = 'Y'
            counts[idx] -= 1

    return ''.join(result)

Time complexity: O(n). Space complexity: O(1) auxiliary space (excluding the output string).

Hints

First mark every exact match as `G`. Those target positions cannot be reused for `Y`.
Count only the letters from target that were not matched as `G`, then scan the remaining guess positions and assign `Y` while decrementing counts.

Part 2: Validate future guesses using past information

You are given a fixed lowercase `target` word and a list of `guesses`, all of the same length. Process guesses in order. A guess is `invalid_input` if it contains any letter that was previously confirmed absent from the target. Otherwise, evaluate it using Wordle-like feedback: `G` for exact match, `Y` for a letter that appears in another unmatched target position, and `W` otherwise. After evaluating a valid guess, a letter becomes confirmed absent if every occurrence of that letter in that guess received `W`. If a guess is invalid, it is not evaluated and it does not update the learned information. Return the result for every round.

Constraints

1 <= len(target) <= 100000
0 <= len(guesses)
Each guess contains only lowercase English letters and has length equal to len(target).
The sum of lengths of all guesses is at most 200000.

Examples

Input: ('maple', ['cable', 'cazle', 'zzzzz'])

Expected Output: ['WGWGG', 'invalid_input', 'WWWWW']

Explanation: After `cable`, letters `c` and `b` are confirmed absent. `cazle` is invalid because it contains `c`. Invalid guesses do not teach anything, so `zzzzz` is still evaluated normally.

Input: ('abca', ['aaaa', 'dada'])

Expected Output: ['GWWG', 'WYWG']

Explanation: In round 1, letter `a` is not confirmed absent because it has green positions. Therefore round 2 is valid even though it contains `a`.

Input: ('maple', ['zzzzz', 'fuzzy'])

Expected Output: ['WWWWW', 'invalid_input']

Explanation: All `z` characters are white in round 1, so `z` is confirmed absent. The next guess is invalid because it contains `z`.

Input: ('a', ['b', 'a', 'b'])

Expected Output: ['W', 'G', 'invalid_input']

Explanation: Single-character edge case: after the first round, `b` is known to be absent, so the third guess is invalid.

Input: ('abc', [])

Expected Output: []

Explanation: No guesses means no rounds to evaluate.

Solution

def solution(target, guesses):
    n = len(target)

    def feedback(guess):
        counts = [0] * 26
        result = ['W'] * n

        for i in range(n):
            if guess[i] == target[i]:
                result[i] = 'G'
            else:
                counts[ord(target[i]) - 97] += 1

        for i in range(n):
            if result[i] == 'G':
                continue
            idx = ord(guess[i]) - 97
            if counts[idx] > 0:
                result[i] = 'Y'
                counts[idx] -= 1

        return ''.join(result)

    absent = [False] * 26
    answers = []

    for guess in guesses:
        invalid = False
        for ch in guess:
            if absent[ord(ch) - 97]:
                invalid = True
                break

        if invalid:
            answers.append('invalid_input')
            continue

        status = feedback(guess)
        answers.append(status)

        seen = [False] * 26
        has_non_white = [False] * 26

        for ch, mark in zip(guess, status):
            idx = ord(ch) - 97
            seen[idx] = True
            if mark != 'W':
                has_non_white[idx] = True

        for idx in range(26):
            if seen[idx] and not has_non_white[idx]:
                absent[idx] = True

    return answers

Time complexity: O(total_characters_in_all_guesses). Space complexity: O(1) auxiliary space (excluding the returned list and feedback strings).

Hints

Keep a set or 26-length boolean array for letters already proven absent. Check that before evaluating each new guess.
To decide which letters become absent after a valid round, look at each distinct letter in that guess: if none of its positions were marked `G` or `Y`, then that letter is confirmed absent.

Quick Overview

This question evaluates string manipulation, multiset/frequency tracking, and stateful validation across rounds, with particular emphasis on handling repeated letters and multiplicity constraints in feedback generation.