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.

Evaluate word-guess feedback with repeats

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`.

Hints

  1. First mark every exact match as `G`. Those target positions cannot be reused for `Y`.
  2. 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`.

Hints

  1. Keep a set or 26-length boolean array for letters already proven absent. Check that before evaluating each new guess.
  2. 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.

Loading coding console...