SyntaxPilot
Courses/C++ Coding Questions/Lesson 17
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 17 of 30

Queue and deque questions

queue using two stacks (amortised O(1))sliding window maximum (deque)first non-repeating character in a stream

These are the notes for C++ Coding Questions, episode 17, placement practice for people who finished the SyntaxPilot C++ course. The stack's partner, the queue, and the deque that works at both ends, on three classic questions: a queue built from two stacks (and why it is amortised O(1)), the sliding window maximum with a deque of indexes (O(n·k) to O(n)), and the first non-repeating character in a stream (and an if that must be a while).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.

Real-life pictures

In real life In C++
A ticket line: join at the back, leave from the front a queue: FIFO, push, front, pop
A line you can join or leave at both ends a deque: push_front/back, pop_front/back
A teacher's in-tray (newest sheet on top), flipped once into an out-tray (oldest on top) a queue from two stacks
Never flip again while the out-tray still has sheets move only when out.empty()
The hottest day in every 3 days: a hotter newcomer sends cooler earlier days home for good a monotonic deque: pop from the back
The hottest day slides out of the 3 days pop from the front when dq.front() <= i - k
A mela lucky draw: the earliest name entered exactly once wins; names entered twice are out first non-repeating character: a queue of candidates
Several disqualified names at the front: skip all of them while, not if

Queue and deque in one minute

A queue is first in, first out (FIFO): values join at the back and leave from the front.

#include <queue>
queue<int> q;
q.push(5);      // join at the back
q.front();      // read the first one
q.pop();        // remove the first one (returns nothing)
q.empty();  q.size();

A deque (double-ended queue, said "deck") lets you add and remove at both ends:

#include <deque>
deque<int> dq;
dq.push_back(1);  dq.push_front(2);  dq.pop_back();  dq.pop_front();
dq.front();  dq.back();  dq[i];      // it also has indexing

All of these are O(1). Like the stack, front()/pop() on an empty queue is undefined behaviour.

Q1: A queue using two stacks

Problem. Implement a queue with only two stacks. Input: the number of operations, then push x or pop. Print every popped value.

Operations Output
push 1 push 2 push 3 pop pop pop 1 2 3
push 1 push 2 pop push 3 pop pop 1 2 3

Think out loud. One stack (in) takes the pushes; reversing a stack into another one puts the oldest value on top. Edge cases: pushes in between pops. Big test (0 operations): 200,000 pushes then 200,000 pops, printing the sum.

The obvious attempt: move everything there and back on every pop

#include <iostream>
#include <string>
#include <stack>
using namespace std;

struct TwoStackQueue {
    stack<int> in, out;
    void push(int x) { in.push(x); }
    int pop() {
        while (!in.empty()) { out.push(in.top()); in.pop(); }
        int front = out.top(); out.pop();
        while (!out.empty()) { in.push(out.top()); out.pop(); }
        return front;
    }
};

int main() {
    TwoStackQueue q;
    int ops;
    cin >> ops;
    if (ops == 0) {                      // test: 200,000 pushes, then 200,000 pops
        long long sum = 0;
        for (int i = 1; i <= 200000; i++) q.push(i);
        for (int i = 1; i <= 200000; i++) sum += q.pop();
        cout << "sum = " << sum << "\n";
        return 0;
    }
    while (ops--) {
        string op;
        cin >> op;
        if (op == "push") { int x; cin >> x; q.push(x); }
        else cout << q.pop() << " ";
    }
    cout << "\n";
    return 0;
}
1 2 3 

On the big test:

Time Limit Exceeded

Every pop moves the whole queue twice: up to 200,000 values × 2, for 200,000 pops, about 40,000,000,000 moves.

Attempt: don't move back, but flip on every pop

#include <iostream>
#include <string>
#include <stack>
using namespace std;

struct TwoStackQueue {
    stack<int> in, out;
    void push(int x) { in.push(x); }
    int pop() {
        while (!in.empty()) { out.push(in.top()); in.pop(); }
        int front = out.top(); out.pop();
        return front;
    }
};

int main() {
    TwoStackQueue q;
    int ops;
    cin >> ops;
    if (ops == 0) {                      // test: 200,000 pushes, then 200,000 pops
        long long sum = 0;
        for (int i = 1; i <= 200000; i++) q.push(i);
        for (int i = 1; i <= 200000; i++) sum += q.pop();
        cout << "sum = " << sum << "\n";
        return 0;
    }
    while (ops--) {
        string op;
        cin >> op;
        if (op == "push") { int x; cin >> x; q.push(x); }
        else cout << q.pop() << " ";
    }
    cout << "\n";
    return 0;
}
1 2 3 
1 3 2 

1 3 2. After popping 1, the out stack still holds 2. Then 3 is pushed, and the next pop flips again: 3 lands on top of the older 2.

push 1, 2   in: 1 2       pop → flip → out: 2 1 → pop 1 → out: 2
push 3      in: 3         pop → flip → out: 2 3   (3 on top of the older 2!)

Fix: flip only when out is empty

#include <iostream>
#include <string>
#include <stack>
using namespace std;

struct TwoStackQueue {
    stack<int> in, out;
    void push(int x) { in.push(x); }
    int pop() {
        if (out.empty())                 // flip only when out is empty
            while (!in.empty()) { out.push(in.top()); in.pop(); }
        int front = out.top(); out.pop();
        return front;
    }
};

int main() {
    TwoStackQueue q;
    int ops;
    cin >> ops;
    if (ops == 0) {                      // test: 200,000 pushes, then 200,000 pops
        long long sum = 0;
        for (int i = 1; i <= 200000; i++) q.push(i);
        for (int i = 1; i <= 200000; i++) sum += q.pop();
        cout << "sum = " << sum << "\n";
        return 0;
    }
    while (ops--) {
        string op;
        cin >> op;
        if (op == "push") { int x; cin >> x; q.push(x); }
        else cout << q.pop() << " ";
    }
    cout << "\n";
    return 0;
}
1 2 3 

The big test, instantly (1 + 2 + ... + 200,000):

sum = 20000100000

Amortised O(1). One pop can still be slow (when it flips n values), but every value is pushed into in once, moved once, and popped from out once: 3 operations per value. Spread over all operations, each costs O(1) on average. That's what amortised means: the total cost divided by the number of operations. Space O(n).

Q2: Sliding window maximum

Problem. Given n numbers and k, print the maximum of every window of k numbers in a row.

Input Output
1 3 -1 -3 5 3 6 7, k = 3 3 3 5 5 6 7
9 1 2 3, k = 2 9 2 3

Think out loud. There are n − k + 1 windows. Edge cases: the maximum at the very start, k = 1. Big test (0 0): 1,000,000 numbers i % 1000, k = 500,000.

The obvious attempt: rescan every window

#include <iostream>
#include <vector>
using namespace std;

vector<int> windowMax(const vector<int>& a, int k) {
    vector<int> m;
    for (int i = 0; i + k <= (int)a.size(); i++) {
        int best = a[i];
        for (int j = i; j < i + k; j++) best = max(best, a[j]);
        m.push_back(best);
    }
    return m;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 500,000
        n = 1000000; k = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = i % 1000;
    }
    vector<int> m = windowMax(a, k);
    if (n > 20) { cout << m.size() << " windows, last max " << m.back() << "\n"; return 0; }
    for (int x : m) cout << x << " ";
    cout << "\n";
    return 0;
}
3 3 5 5 6 7 

On the big test:

Time Limit Exceeded

500,001 windows × 500,000 numbers ≈ 250,000,000,000 looks. Neighbouring windows share k − 1 numbers, and we scanned them all again.

The idea: a deque of indexes, biggest first

When a new value arrives, every earlier value that is not bigger can never be a window maximum again: the newcomer is at least as big and stays in the window longer. So pop them from the back, then push the new index. The values in the deque then fall from front to back, so the front is the maximum. We store indexes so we can tell how old the front is.

1 3 -1 (k = 3):  1 → [1]   3 → 1 goes home → [3]   -1 → [3 -1]        max 3
-3:              [3 -1 -3]                                            max 3
5:               -3, -1, 3 go home → [5]                              max 5

Attempt: never drop the front

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> windowMax(const vector<int>& a, int k) {
    vector<int> m;
    deque<int> dq;                       // indexes, their values falling
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) m.push_back(a[dq.front()]);
    }
    return m;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 500,000
        n = 1000000; k = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = i % 1000;
    }
    vector<int> m = windowMax(a, k);
    if (n > 20) { cout << m.size() << " windows, last max " << m.back() << "\n"; return 0; }
    for (int x : m) cout << x << " ";
    cout << "\n";
    return 0;
}
3 3 5 5 6 7 

Looks right. But:

9 9 9 

9 9 9: the window 2 3 (indexes 2 and 3) has no 9. Nothing bigger than 9 came, so nothing pushed it out from the back, and nobody checked its age. The first test passed only by luck.

Fix: drop the front once it slides out

The window ending at i is i − k + 1 .. i, so a front index <= i − k is outside it.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

vector<int> windowMax(const vector<int>& a, int k) {
    vector<int> m;
    deque<int> dq;                       // indexes, their values falling
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();   // slid out
        if (i >= k - 1) m.push_back(a[dq.front()]);
    }
    return m;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 500,000
        n = 1000000; k = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = i % 1000;
    }
    vector<int> m = windowMax(a, k);
    if (n > 20) { cout << m.size() << " windows, last max " << m.back() << "\n"; return 0; }
    for (int x : m) cout << x << " ";
    cout << "\n";
    return 0;
}
9 2 3 
3 3 5 5 6 7 

The big test, instantly:

500001 windows, last max 999

O(n) time: each index has one push_back and at most one pop (from the back or the front). O(k) space: the deque never holds more than one window.

Q3: First non-repeating character in a stream

Problem. A stream of characters a–z arrives one by one. After each character, print the first character seen exactly once so far, or # if there is none.

Stream Output
aabc a#bb
zz z#
abba aaa#

Think out loud. Edge cases: nobody left (#), two repeated characters at the front at once. Big test: the word big builds 300,000 as.

The obvious attempt: rescan the stream after every character

#include <iostream>
#include <string>
using namespace std;

string firstUnique(const string& s) {
    string ans;
    int cnt[26] = {};
    for (int i = 0; i < (int)s.size(); i++) {
        cnt[s[i] - 'a']++;
        char first = '#';
        for (int j = 0; j <= i; j++)       // rescan the stream so far
            if (cnt[s[j] - 'a'] == 1) { first = s[j]; break; }
        ans += first;
    }
    return ans;
}

int main() {
    string s;
    while (cin >> s) {
        if (s == "big") s = string(300000, 'a');   // test: 300,000 a's
        string ans = firstUnique(s);
        if (s.size() > 20) cout << ans.size() << " answers, last " << ans.back() << "\n";
        else cout << s << ": " << ans << "\n";
    }
    return 0;
}
aabc: a#bb
zz: z#

On big:

Time Limit Exceeded

After each a, the scan walks the whole stream and finds nothing: about n²/2 = 45,000,000,000 steps.

The idea: a queue of candidates

  • A character seen for the first time joins the back of a queue.
  • The front is the earliest candidate. If its count is now more than 1, it is out: pop it.
  • The answer is q.front(), or # if the queue is empty.
  • A character that is out never comes back, so each character is pushed once and popped at most once.

Attempt: if instead of while

#include <iostream>
#include <string>
#include <queue>
using namespace std;

string firstUnique(const string& s) {
    string ans;
    int cnt[26] = {};
    queue<char> q;                       // candidates, in arrival order
    for (char c : s) {
        if (++cnt[c - 'a'] == 1) q.push(c);
        if (!q.empty() && cnt[q.front() - 'a'] > 1) q.pop();
        ans += q.empty() ? '#' : q.front();
    }
    return ans;
}

int main() {
    string s;
    while (cin >> s) {
        if (s == "big") s = string(300000, 'a');   // test: 300,000 a's
        string ans = firstUnique(s);
        if (s.size() > 20) cout << ans.size() << " answers, last " << ans.back() << "\n";
        else cout << s << ": " << ans << "\n";
    }
    return 0;
}
aabc: a#bb
zz: z#
abba: aaab

abba ends with b, but b was entered twice. At the last a, the queue is a b and both counts are 2. The if pops a and stops; the new front b is out too. (When the second b came, b was not at the front, so nobody popped it then.)

Fix: while

#include <iostream>
#include <string>
#include <queue>
using namespace std;

string firstUnique(const string& s) {
    string ans;
    int cnt[26] = {};
    queue<char> q;                       // candidates, in arrival order
    for (char c : s) {
        if (++cnt[c - 'a'] == 1) q.push(c);
        while (!q.empty() && cnt[q.front() - 'a'] > 1) q.pop();
        ans += q.empty() ? '#' : q.front();
    }
    return ans;
}

int main() {
    string s;
    while (cin >> s) {
        if (s == "big") s = string(300000, 'a');   // test: 300,000 a's
        string ans = firstUnique(s);
        if (s.size() > 20) cout << ans.size() << " answers, last " << ans.back() << "\n";
        else cout << s << ": " << ans << "\n";
    }
    return 0;
}
aabc: a#bb
zz: z#
abba: aaa#

On big, instantly:

300000 answers, last #

O(n) time, O(26) = O(1) extra space (26 counts and at most 26 candidates).

Stack, queue or deque?

Use When the next thing to handle is Examples
stack the newest brackets, undo, next greater element
queue the oldest ticket lines, printer jobs, first unique character, BFS
deque removed from both ends sliding window maximum, palindromes, 0-1 BFS

And whenever many things can become useless at once (too small at the back, out at the front), pop with while, not if.

Complexity summary

Program Time Extra space
two-stack queue, move back every pop O(n) per pop: TLE O(n)
two-stack queue, flip only when empty O(1) amortised per op O(n)
window max, rescan O(n · k): TLE O(1)
window max, deque of indexes O(n) O(k)
first unique, rescan O(n²): TLE O(26)
first unique, queue + counts O(n) O(26)

Common mistakes (and the real results)

Mistake What you see Why Fix
moving everything back after every pop Time Limit Exceeded O(n) per pop leave out as it is
flipping when out isn't empty 1 3 2 new values jump over older ones if (out.empty()) flip
never dropping the deque's front 9 9 9 for 9 1 2 3, k = 2 an old maximum stays if (dq.front() <= i - k) dq.pop_front();
storing values in the deque can't tell the front's age values aren't positions store indexes
reading the window max before i >= k - 1 extra "windows" of fewer than k values the first window isn't full if (i >= k - 1)
if to skip repeated candidates abba: aaab only one is skipped while
q.front() on an empty queue undefined behaviour nobody is left print # when q.empty()
q.pop() used as a value error: void value not ignored as it ought to be pop() returns void x = q.front(); q.pop();

Your turn: reverse the first k of a queue (solution)

Problem. Reverse the first k values of a queue, using only a queue and a stack. 1 2 3 4 5, k = 3 → 3 2 1 4 5.

Idea. Pop k values into a stack (reversing them), push them back into the queue (now at the back), then move the other n − k values from the front to the back.

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

void reverseFirstK(queue<int>& q, int k) {
    stack<int> st;
    for (int i = 0; i < k; i++) { st.push(q.front()); q.pop(); }
    while (!st.empty()) { q.push(st.top()); st.pop(); }
    for (int i = 0; i < (int)q.size() - k; i++) { q.push(q.front()); q.pop(); }
}

int main() {
    int n, k;
    while (cin >> n >> k) {
        queue<int> q;
        for (int i = 0; i < n; i++) { int x; cin >> x; q.push(x); }
        reverseFirstK(q, k);
        while (!q.empty()) { cout << q.front() << " "; q.pop(); }
        cout << "\n";
    }
    return 0;
}

5 3 / 1 2 3 4 5, 4 4 / 10 20 30 40, 3 1 / 7 8 9:

3 2 1 4 5 
40 30 20 10 
7 8 9 

O(n) time, O(k) extra space.

Practice questions (with solutions)

1. Binary numbers from 1 to n with a queue.

Solution

Start with "1"; each time, pop a string s, print it, and push s + "0" and s + "1". The queue produces them in increasing order.

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    queue<string> q;
    q.push("1");
    for (int i = 0; i < n; i++) {
        string s = q.front(); q.pop();
        cout << s << " ";
        q.push(s + "0");
        q.push(s + "1");
    }
    cout << "\n";
    return 0;
}

Input 10:

1 10 11 100 101 110 111 1000 1001 1010 

2. First negative number in every window of k. Print 0 for a window with no negative number.

Solution

A queue of the indexes of negative numbers; drop indexes that slid out of the window; the front is the answer.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    queue<int> neg;                      // indexes of negatives, oldest first
    for (int i = 0; i < n; i++) {
        if (a[i] < 0) neg.push(i);
        while (!neg.empty() && neg.front() <= i - k) neg.pop();
        if (i >= k - 1) cout << (neg.empty() ? 0 : a[neg.front()]) << " ";
    }
    cout << "\n";
    return 0;
}

Input 8 3 / 12 -1 -7 8 -15 30 16 28:

-1 -1 -7 -15 -15 0 

3. A stack using two queues.

Solution

To push x: put it into the empty queue q2, move everything from q1 behind it, then swap q1 and q2. Now q1.front() is always the newest value. Push O(n), pop O(1).

#include <iostream>
#include <queue>
using namespace std;

struct QueueStack {
    queue<int> q1, q2;
    void push(int x) {
        q2.push(x);
        while (!q1.empty()) { q2.push(q1.front()); q1.pop(); }
        swap(q1, q2);
    }
    int pop() { int x = q1.front(); q1.pop(); return x; }
    bool empty() const { return q1.empty(); }
};

int main() {
    QueueStack s;
    for (int x : {1, 2, 3}) s.push(x);
    cout << s.pop() << " ";
    s.push(4);
    while (!s.empty()) cout << s.pop() << " ";
    cout << "\n";
    return 0;
}
3 4 2 1 

4. Is a word a palindrome? Use a deque.

Solution

Put the letters in a deque and compare front() and back(), popping both, until fewer than two are left.

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        deque<char> dq(s.begin(), s.end());
        bool ok = true;
        while (dq.size() > 1) {
            if (dq.front() != dq.back()) { ok = false; break; }
            dq.pop_front();
            dq.pop_back();
        }
        cout << s << ": " << (ok ? "palindrome" : "no") << "\n";
    }
    return 0;
}
malayalam: palindrome
deque: no
level: palindrome
abca: no

Mini project: a printer queue

Jobs arrive (add <name> <pages>); the printer prints 5 pages per tick (tick) from the oldest job; status shows the waiting jobs. A queue keeps the order fair.

#include <iostream>
#include <string>
#include <queue>
using namespace std;

struct Job { string name; int pages; };

int main() {
    queue<Job> q;
    string cmd;
    int tick = 0;
    while (cin >> cmd) {
        if (cmd == "add") {
            Job j;
            cin >> j.name >> j.pages;
            q.push(j);
        } else if (cmd == "tick") {
            tick++;
            int budget = 5;                  // pages per tick
            while (budget > 0 && !q.empty()) {
                int done = min(budget, q.front().pages);
                q.front().pages -= done;
                budget -= done;
                if (q.front().pages == 0) {
                    cout << "tick " << tick << ": finished " << q.front().name << "\n";
                    q.pop();
                }
            }
        } else {
            cout << "waiting: " << q.size();
            if (!q.empty()) cout << ", next " << q.front().name << " (" << q.front().pages << " pages left)";
            cout << "\n";
        }
    }
    return 0;
}
waiting: 3, next notes (7 pages left)
waiting: 3, next notes (2 pages left)
tick 2: finished notes
tick 2: finished resume
tick 3: finished ticket
waiting: 0

Quick quiz

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(3);
    dq.pop_back();
    dq.push_front(4);
    cout << dq.front() << " " << dq.back() << " " << dq.size() << "\n";
    return 0;
}

(A) 4 1 3 (B) 4 2 3 (C) 3 1 3 (D) 1 4 3

Answer

(A) 4 1 3. [1] → [1 2] → [3 1 2] → pop_back → [3 1] → push_front(4) → [4 3 1].

4 1 3

Interview questions

  1. Queue vs stack? A queue removes the oldest value (FIFO); a stack removes the newest (LIFO).
  2. What is a deque and what does std::deque cost? A double-ended queue: O(1) push/pop at both ends and O(1) indexing.
  3. How do you build a queue from two stacks? Push onto in; to pop, if out is empty move everything from in to out, then pop out.
  4. Why is that amortised O(1)? Each value is moved from in to out at most once, so n operations cost O(n) in total even though a single pop can cost O(n).
  5. What does amortised mean? The cost averaged over a whole sequence of operations, not the worst single operation.
  6. Why does the sliding window maximum use a deque, not a heap? A deque gives O(n) total; a heap needs O(n log k) and lazy deletion of old values.
  7. Why store indexes in the deque? To know when the front has slid out of the window (front <= i - k).
  8. Why is the window maximum O(n) with a while inside the loop? Every index is pushed once and popped at most once.
  9. First non-repeating character: why a queue? Candidates are needed in arrival order, and the earliest one is checked first.
  10. What does std::queue use underneath? A std::deque by default (like std::stack).

Glossary

Term Meaning Example
Queue A container where values join at the back and leave from the front a ticket line
FIFO First in, first out the first in line is served first
std::queue The C++ queue adaptor, from <queue> queue<int> q; q.push(5);
front() Reads the first (oldest) value of a queue or deque q.front()
Deque A double-ended queue: add and remove at both ends deque<int> dq;
push_front / pop_back Add at the front / remove from the back of a deque dq.push_front(3);
Amortised O(1) O(1) on average over all operations, though one may be slow the two-stack queue
Sliding window maximum The largest value in every window of k in a row 3 3 5 5 6 7
Monotonic deque A deque whose values stay sorted, by popping before each push values fall front to back
Window The k positions i − k + 1 .. i indexes 2..3 for i = 3, k = 2
Stream Data that arrives one piece at a time characters typed one by one
Non-repeating character A character seen exactly once so far b in aab
Candidate A value that could still be the answer names still in the lucky draw
Time Limit Exceeded (TLE) The judge stopped a program that ran too long O(n · k) on a million numbers

Summary

  • Queue: FIFO, push/front/pop; deque: both ends, O(1); never front() an empty one.
  • Queue from two stacks: push to in; pop from out, flipping in into out only when out is empty. Amortised O(1).
  • Sliding window maximum: a deque of indexes; pop the back while not bigger, pop the front once <= i − k; the front is the max. O(n).
  • First non-repeating character: counts + a queue of first-time characters; while the front is repeated, pop. O(n).

Next episode: Heap questions: the k largest elements (a min-heap of size k), the k-th smallest, and merging k sorted vectors with priority_queue and greater<>.