Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
A uniform substring is a run of one repeated character; its weight is the character's alphabet position (a=1…z=26) times the run length. Precompute every achievable weight in a single left-to-right pass — keep a running sum that resets when the character changes and adds the char weight when it repeats — storing each running value in a hash set. Then answer each query in O(1) by membership test. O(n + q) time, O(n) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you separate one-time preprocessing from per-query work, and whether you correctly enumerate every prefix of each run (not just the full run) into the lookup set.
Where candidates slip
Only inserting the full run's weight (missing shorter prefixes), or recomputing weights per query for an O(n·q) blow-up.
How to stand out
Frame it as 'precompute the achievable-weight set in O(n), then O(1) per query', and note each step of the running sum already represents a valid uniform-substring weight, so insertion is free.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewScan sc == prev?YesNoExplore the full treeCollapse the tree
How to read it:A single resettable running sum visits every achievable uniform weight.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Recompute Runs Per Query (Brute Force)
1Hint 1Explore hintHide hint
A query asks 'is there a run prefix weighing exactly q?'. How would you answer one query directly?
2Hint 2Explore hintHide hint
For a single query, scan the runs and check if any prefix weight equals it.
3Hint 3Explore hintHide hint
Doing that independently for each of q queries rescans the whole string q times — O(n·q).
A · Core idea
Answer each query in isolation: walk the runs of s, maintaining a running weight, and report "Yes" the moment a running value equals the query (else "No").
Why it's correct. It directly checks the achievability condition for the one query in hand.
Why we improve it. The set of achievable weights does not change between queries, yet this recomputes it from scratch every time. With up to 10⁵ queries over a 10⁵ string that's 10¹⁰ operations — far too slow. The fix is to compute the achievable set once and reuse it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "aaa", queries = [3, 4]Array state
run a
running 1 → 2 → 3
["Yes", "No"]C · Code with teaching comments
Reference implementation previewpublic List<String> weightedUniformStrings(String s, int[] queries) { List<String> res = new ArrayList<>(); for (int q : queries) { boolean found = false; int running = 0;Explore the full codeHide the full code
D · Why it works and complexityO(n · q) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Repeated identical scans are a flashing sign to precompute. The achievable-weight set is query-independent, so building it a single time and caching converts O(n·q) into O(n + q).
ComplexityO(n · q) time, O(1) space — Each query triggers a full O(n) scan of the runs; with q queries that's O(n·q). Only O(1) extra space since nothing is cached.
E · Edge cases and pitfalls5queries = [] — No queries → empty result, no scans.Explore edge casesHide edge cases
Edge cases handled
queries = []No queries → empty result, no scans.s = "z", q = 26Single 'z' weighs 26 → Yes.
Pitfalls
- Rescanning the string for every query — O(n·q) is too slow at 10⁵ each.
- Forgetting to reset running on a character change.
- Off-by-one in char weight (use c−'a'+1).
Approach 2 of 2 · Optimal
Precompute Achievable-Weight Set (Optimal)
1Hint 1Explore hintHide hint
The achievable weights don't depend on the queries. What if you computed them all once?
2Hint 2Explore hintHide hint
Scan s once; keep a running sum that adds w(c) when the char repeats and resets to w(c) otherwise. Insert every running value into a set.
3Hint 3Explore hintHide hint
Each query is then just a set membership test → O(1).
A · Core idea
Make one left-to-right pass. Track running (the weight of the current run prefix) and prev (the previous character). For each character c: if c == prev, extend the run with running += w(c); otherwise start a new run with running = w(c). After updating, insert running into a hash set. Once the pass is done, answer each query with a single membership check.
Why each intermediate value matters. Inside a run of c of length L, the prefixes have weights w(c)·1, w(c)·2, …, w(c)·L. The running sum hits each of those in turn, so inserting it at every step records every achievable uniform-substring weight — not just the full run. Inserting only the final running would miss the shorter prefixes and produce wrong "No"s.
Why the reset is essential. When the character changes, the previous run ends; the new run's weights start fresh from w(c). Failing to reset would chain unrelated runs together and fabricate weights that no uniform substring actually has.
Why a set. Different runs can yield identical weights ("bb" and "d" both weigh 4). We only care whether a weight is achievable, so a set deduplicates naturally and gives O(1) lookups.
Why this is the right complexity split. Preprocessing is paid once (O(n)); each query is O(1). That's the canonical 'build an index, then serve fast lookups' trade, ideal when queries are numerous.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "abccddde", queries = [1, 3, 12, 5, 9, 10]Array state
a b c c
1 | 2 | 3 | 6
["Yes", "Yes", "Yes", "Yes", "No", "No"]C · Code with teaching comments
D · Why it works and complexityO(n + q) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The achievable-weight set is a tiny precomputed index over the string. Whenever queries are independent of each other and depend only on a fixed structure, compute that structure once and serve queries in O(1) — the same idea behind prefix sums and hashed lookups.
ComplexityO(n + q) time, O(n) space — Building the set is one O(n) pass with O(1) work per character. Each of the q queries is an O(1) set lookup → O(n + q) total. The set holds at most n distinct values → O(n) space.
E · Edge cases and pitfalls6s = "aaa", q = 4 — Run weights {1,2,3}; 4 unreachable → No.Explore edge casesHide edge cases
Edge cases handled
s = "aaa", q = 4Run weights {1,2,3}; 4 unreachable → No.s = "aba", q = 2Weights {1,2} (the lone 'b' weighs 2) → Yes.duplicate weight "bbd""bb"=4 and "d"=4 both insert 4; set dedups → single entry.
Pitfalls
- Inserting only the full run's weight, missing shorter-prefix weights.
- Forgetting to reset running when the character changes.
- Recomputing weights per query instead of caching the set.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<String> weightedUniformStrings(String s, int[] queries) { Set<Integer> seen = new HashSet<>(); int running = 0; char prev = 0; for (int i = 0; i < s.length(); i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Missing prefix weights
A uniform substring can be any prefix of a run, so "ddd" yields 4, 8, AND 12. Inserting only the final 12 makes queries for 4 or 8 wrongly answer No.
Explore the code comparisonHide the code comparison
Missing prefix weights
A uniform substring can be any prefix of a run, so "ddd" yields 4, 8, AND 12. Inserting only the final 12 makes queries for 4 or 8 wrongly answer No.
Don't write this
# only the full run
run_len = ...
seen.add(w * run_len)Write this instead
running = running + w if c == prev else w
seen.add(running) # every step2Not resetting across runs
Without the reset, the running sum carries over from a previous character, producing weights that no single-character substring actually has.
Explore the code comparisonHide the code comparison
Not resetting across runs
Without the reset, the running sum carries over from a previous character, producing weights that no single-character substring actually has.
Don't write this
running += (c - 'a' + 1);
seen.add(running);Write this instead
running = (c == prev) ? running + (c - 'a' + 1) : (c - 'a' + 1);
seen.add(running);3Per-query rescanning
The achievable set is query-independent. Recomputing it for each query turns O(n + q) into O(n·q), which TLEs at 10⁵ queries.
Explore the code comparisonHide the code comparison
Per-query rescanning
The achievable set is query-independent. Recomputing it for each query turns O(n + q) into O(n·q), which TLEs at 10⁵ queries.
Don't write this
for q in queries:
...scan whole string...Write this instead
# build seen once
return ['Yes' if q in seen else 'No' for q in queries]Revise
Carry the pattern into the interview
Pattern to remember
Run-length prefix sums into a set
Code pattern to memorize
running = 0; prev = ''
for c in s:
running = running + w(c) if c == prev else w(c)
seen.add(running); prev = c
for q in queries: answer 'Yes' if q in seen else 'No'Rules to remember
- 1Weight of a uniform substring =
charWeight × runLength, wherew(a)=1 … w(z)=26. - 2Only contiguous runs of the same character are uniform —
"ab"is never uniform. - 3Accumulate within a run (
running += w(c)) and reset tow(c)when the character changes. - 4Store every intermediate running value — each prefix of a run is itself a valid uniform substring.
- 5Precompute the set once, then every query is an O(1) membership check.
Use this pattern when
- Many queries against properties of contiguous same-character runs
- You can enumerate all achievable values cheaply and cache them
- Membership ('is this value achievable?') is the question, not reconstruction
- Per-query latency must be O(1) after preprocessing
Choose another pattern when
- Substrings need not be uniform → run-length precompute doesn't capture them
- Few queries, huge value space → maybe compute per-query instead of caching all
- You must return the substring, not yes/no → store positions, not just weights
- Weights depend on order or position, not just char and length → different model
Interview takeaway
When a problem fires many membership queries against a derivable set of values, precompute the whole set once and answer each query in O(1). Here the set is every prefix-weight of every same-character run, built in one pass with a resettable running sum.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPrecompute-then-query with a hash set. When numerous independent queries test membership against a fixed derivable set, build the set once in O(n) and serve each query in O(1). Here the set is every prefix-weight of every same-character run, produced by a resettable running sum.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Sparse ArraysSame precompute-then-query shape: build a frequency map once, answer membership counts in O(1).
- Subarray Sum Equals KComing soonPrefix sums cached in a map — the same 'precompute running values' idea on subarrays.
- Longest Uniform RunComing soonTrack the longest run length during the same single pass.
- Range Sum Query - ImmutableComing soonClassic precompute-prefix-then-O(1)-query pattern.