Unique String Window - FAANG Problems | Repovive

FNG4. Unique String Window

1s256 MB

This problem is based on a Netflix interview problem described here.

Given an array of strings, find the longest contiguous subarray that contains no repeated string.

If several windows have the same length, choose the earliest window.

Constraints

$0 \le n \le 60000$
Strings contain no whitespace
Total input characters are at most $1000000$

Input

\begin{array}{l} n \\ word_1 \quad word_2 \quad \cdots \quad word_n \end{array}

Output

Print length start end using zero-based indexes, then print the window on the next line. For an empty array, print 0 -1 -1 and then an empty line.

Samples

Input

5
a b c a d

Explanation

\begin{array}{l} \\ \text{1. Identify Maximum Unique Window Length:} \\ \quad \bullet \text{ Window } [a, \; b, \; c] \implies \text{Length } 3 \\ \quad \bullet \text{ Window } [b, \; c, \; a, \; d] \implies \text{Length } \mathbf{4 \quad (\text{Max Possible Length})} \\ \\ \text{2. Coordinate Extraction:} \\ \quad \bullet \text{ Start Index } (b) = \mathbf{1} \\ \quad \bullet \text{ End Index } (d) = \mathbf{4} \\ \\ \hline \text{\textbf{Output Line 1: }} \text{4 1 4} \\ \text{\textbf{Output Line 2: }} \text{b c a d} \end{array}

Output

4 1 4
b c a d

Input

3
x x x

Explanation

\begin{array}{l} \\ \text{1. Identify Maximum Unique Window Length:} \\ \quad \bullet \text{ Any window of length } \ge 2 \text{ (e.g., } [x, \; x] \text{) introduces duplicates.} \\ \quad \bullet \text{ Max Valid Unique Length } = \mathbf{1} \\ \\ \text{2. Tie-Breaking Mechanics for Earliest Window:} \\ \quad \bullet \text{ Window 1: } [x] \text{ at index range } [0, \; 0] \implies \mathbf{\text{Earliest Occurrence \checkmark}} \\ \quad \bullet \text{ Window 2: } [x] \text{ at index range } [1, \; 1] \implies \text{Ignored (Later)} \\ \quad \bullet \text{ Window 3: } [x] \text{ at index range } [2, \; 2] \implies \text{Ignored (Later)} \\ \\ \hline \text{\textbf{Output Line 1: }} \text{1 0 0} \\ \text{\textbf{Output Line 2: }} \text{x} \end{array}

Output

1 0 0
x

$0 \le n \le 60000$
Strings contain no whitespace
Total input characters are at most $1000000$

\begin{array}{l} n \\ word_1 \quad word_2 \quad \cdots \quad word_n \end{array}

\begin{array}{l} \\ \text{1. Identify Maximum Unique Window Length:} \\ \quad \bullet \text{ Window } [a, \; b, \; c] \implies \text{Length } 3 \\ \quad \bullet \text{ Window } [b, \; c, \; a, \; d] \implies \text{Length } \mathbf{4 \quad (\text{Max Possible Length})} \\ \\ \text{2. Coordinate Extraction:} \\ \quad \bullet \text{ Start Index } (b) = \mathbf{1} \\ \quad \bullet \text{ End Index } (d) = \mathbf{4} \\ \\ \hline \text{\textbf{Output Line 1: }} \text{4 1 4} \\ \text{\textbf{Output Line 2: }} \text{b c a d} \end{array}

\begin{array}{l} \\ \text{1. Identify Maximum Unique Window Length:} \\ \quad \bullet \text{ Any window of length } \ge 2 \text{ (e.g., } [x, \; x] \text{) introduces duplicates.} \\ \quad \bullet \text{ Max Valid Unique Length } = \mathbf{1} \\ \\ \text{2. Tie-Breaking Mechanics for Earliest Window:} \\ \quad \bullet \text{ Window 1: } [x] \text{ at index range } [0, \; 0] \implies \mathbf{\text{Earliest Occurrence \checkmark}} \\ \quad \bullet \text{ Window 2: } [x] \text{ at index range } [1, \; 1] \implies \text{Ignored (Later)} \\ \quad \bullet \text{ Window 3: } [x] \text{ at index range } [2, \; 2] \implies \text{Ignored (Later)} \\ \\ \hline \text{\textbf{Output Line 1: }} \text{1 0 0} \\ \text{\textbf{Output Line 2: }} \text{x} \end{array}