SDE - 1

Step 1 — Count frequencies of scores: traverse points[] and build a map cnt[score] = frequency.
Step 2 — Create a sorted list g of (score, need) pairs sorted by score ascending. This ensures we assign values in increasing score order (requirement for strictly increasing assigned values).
Step 3 — Count frequencies of values[] into an ordered map/multiset freq where keys are value buckets and values are available counts. Using an ordered map lets us quickly find the next value > prev.
Step 4 — Greedy assignment: maintain prev = -inf. For each (score, need) in sorted g:

Find the smallest val in freq such that val > prev and freq[val] >= need.

If found, decrement freq[val] by need, set pick[score] = val, and update prev = val.

If not found, assignment is impossible (handle gracefully).
Step 5 — Build result: for each original points[i], set ans[i] = pick[points[i]]. Return ans.

Why greedy works: assigning the smallest valid value for each score preserves maximum remaining large values for later (higher) scores and satisfies the strictly-increasing constraint.

Time & Space Complexity:

Counting and building g: O(n).

Sorting g: O(k log k) where k = # unique scores.

Using an ordered map for values and iterating: in worst case O(k * log m) where m = # unique values.

Overall roughly O(n + k log k + m log m). Space O(n + m).

Step 1 — Build prefix sums pref[] over trans[] (1-indexed): pref[i] = sum(trans[0..i-1]). Total loop time total = pref[m].
Step 2 — Define helper cwDist(u, v) to compute clockwise distance from station u to station v using the prefix sums and modulo total arithmetic:

If stations are 1-indexed and u <= v: diff = pref[v-1] - pref[u-1].

Otherwise wrap-around: compute similarly and normalize. Use ((diff % total) + total) % total.
Step 3 — Iterate through req[] with current station cur = 1. For each next required station h:

Compute clockwise distance cw = cwDist(cur, h) and counter-clockwise distance ccw = total - cw.

Add min(cw, ccw) to ans.

Set cur = h.
Step 4 — Return ans.

Why it works: prefix sums give O(1) distance queries on the circular track; choosing min(cw, total-cw) ensures minimal travel per leg.

Time & Space Complexity:

Prefix sums: O(m).

For each required station, O(1) work; total O(|req|).

Space O(m) for prefix array.

Stepwise — Optimal solution I should have given (and you can present):

Step 1 — Recognize pattern (sliding window + frequency):
We need the longest window [l..r] where we can change at most k characters to make all characters in the window identical. That means window_size - max_freq_in_window <= k, where max_freq_in_window is the count of the most frequent character inside the current window.

Step 2 — Maintain a sliding window:
Use two pointers l = 0, r = 0 and expand r across the string. Maintain a frequency array/map count[26] for characters and an integer maxf = maximum frequency in the current window (the highest count[c] among characters present).

Step 3 — Check window validity:
At every step, window size = r - l + 1. If window_size - maxf <= k, the window is valid — update global answer ans = max(ans, window_size).
If invalid (window_size - maxf > k), move l forward (count[s[l]]--) and shrink the window until it becomes valid.

Step 4 — Note about maxf maintenance:
maxf can be kept as the maximum frequency seen so far in the current window. When we increment count[s[r]], update maxf = max(maxf, count[s[r]]). It's safe to leave maxf possibly larger than the true current-window maximum on some shrink steps — the correctness still holds because the condition window_size - maxf <= k becoming false will force l forward; using this relaxed maxf still gives correct ans and keeps overall algorithm O(n). (Alternatively, recompute maxf occasionally at cost O(26) if strictness is preferred.)

Step 5 — Return the answer once r has scanned the string.

Complexity:

Time: O(n) — each r and l move at most n steps, and character map is O(1) (26 letters).

Space: O(1) — fixed-size frequency array (or O(alphabet) generally).