Katkat
Back

Solve Wonderful Strings and Grid Queries

UberSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize string transformations using bitmask dynamic programming and to perform efficient range-based queries on a grid using a 2D data structure or sweep-line approach.

Part 1: Wonderful String Transformation

You are given a string s consisting only of the first 10 lowercase English letters ('a' through 'j'). A string is considered "wonderful" if the count of every character present in the string is even. You want to make a substring s[i...j] wonderful by changing the minimum number of characters.

Given the string s, implement a function min_changes_to_wonderful(s) that returns the minimum number of characters to change in a substring to make it wonderful. Since this must be efficient, consider how the parity of character counts can be represented using bitmasks.

Part 2: Grid Reachability Queries

Consider a grid of size N x N where each cell (r, c) contains an integer value V[r][c]. You receive Q queries. Each query consists of a rectangle defined by (r1, c1) and (r2, c2) and a threshold K. For each query, return the count of cells within that rectangle where V[r][c] >= K.

Constraints:

  • N up to 1000.
  • Q up to 100,000.
  • s length up to 100,000.

Examples

Part 1: Input: s = "abcabc" Output: 0 (The entire string is already wonderful as each letter appears twice).

Part 2: Input: grid = [[1, 5], [2, 8]], Query: (0, 0) to (1, 1) with K = 5 Output: 2 (Cells with values 5 and 8 satisfy the condition).

Hints

Hint 1

For the string problem, represent the parity of the 10 characters as a bitmask of length 10, where the i-th bit is 1 if the character count is odd and 0 if even.

Hint 2

For the string problem, use a prefix XOR mask approach: a substring `[i...j]` is wonderful if `prefix_mask[j] ^ prefix_mask[i-1] == 0`.

Hint 3

For the grid queries, since the threshold `K` varies, process queries offline by sorting them by `K` and use a 2D Fenwick tree or a sweep-line algorithm with a 1D segment tree.

Follow-up questions

  • How would you modify the string transformation if you were allowed to delete characters instead of changing them?
  • If the grid values were updated dynamically between queries, which data structure would be most efficient to maintain for the reachability queries?
  • Can you explain the trade-offs between using a 2D Fenwick tree versus a Persistent Segment Tree for the grid problem in terms of space complexity?