Even Out the Four Keys

Medium

A typing trainer logs presses of four keys: Q, W, E and R. A log keys of length n (a multiple of 4) is **even** when each of the four keys appears in it exactly n / 4 times. You may pick one contiguous chunk of the log and overwrite it with any other string of the same length made of these four letters. What is the shortest chunk that makes the log even? If it is already even, the answer is 0.

Example 1

keys='QWERRWEQ' → 0

Every key appears exactly twice, so the log is already even and nothing needs changing.

Example 2

keys='WWWWQERR' → 2

Each key should appear twice. There are two extra Ws and one Q and one E missing. Rewrite the first two Ws as Q and E: "QEWWQERR".

Example 3

keys='RWRQ' → 1

One R is extra and E is missing, so replacing a single R with E is enough.

Constraints

4 ≤ len(keys) ≤ 10⁵
len(keys) is a multiple of 4
keys contains only the letters Q, W, E, R

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Sliding Window

Similar problems

Longest Repeat-Free Stretch Medium Two-Letter Stretch Medium Recurring Gene Windows Medium Window with Few Kinds of Letters Medium Every Letter at Least k Times Medium

Input

keys='QWERRWEQ'

Expected

Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.