How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Netflix.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Netflix during technical interviews.

Solve sliding-window and disjoint-string-pairs tasks

Q: Solve sliding-window and disjoint-string-pairs tasks

This question evaluates proficiency in string-processing algorithms, sliding-window techniques, efficient set or bitmask representations, and combinatorial pair counting under strict time and space constraints.

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Task A (Sliding Window) Given a string `s`, find the length of the longest contiguous substring that contains **no repeated characters**. - **Input:** a string `s` - **Output:** an integer (maximum length) - **Constraints (assume):** `1 <= len(s) <= 2e5`; ASCII characters. ## Task B (Disjoint-character string pairs) Given a list of strings `words`, count the number of **unique unordered pairs** `(i, j)` with `i < j` such that `words[i]` and `words[j]` share **no common characters**. - Two strings “share no common characters” if there is no character `c` that appears in both strings. - Count each pair once (order doesn’t matter). ### Example Input: `["apple", "banana", "peach", "kiwi"]` Valid unique pairs include: - ("apple", "kiwi") - ("banana", "kiwi") - ("peach", "kiwi") ### Requirements Design an algorithm with time complexity **O(n log n)** (or better) where `n = len(words)`. - **Input:** list of strings `words` - **Output:** integer count of valid pairs - **Constraints (assume):** `1 <= n <= 2e5`; each word length up to `1e3`; characters are lowercase `a`–`z` (state any additional assumptions you need).

Quick Answer: This question evaluates proficiency in string-processing algorithms, sliding-window techniques, efficient set or bitmask representations, and combinatorial pair counting under strict time and space constraints.

Part 1: Longest Substring Without Repeating Characters

Given a string `s`, return the length of the longest contiguous substring that contains no repeated characters. A substring must be contiguous. If the input string is empty, return `0`.

Constraints

0 <= len(s) <= 2 * 10^5
Characters are ASCII
Your algorithm should run in O(n) time

Examples

Input: "abcabcbb"

Expected Output: 3

Explanation: The longest valid substring is "abc", which has length 3.

Input: "bbbbb"

Expected Output: 1

Explanation: Every substring with unique characters can contain only one 'b'.

Input: ""

Expected Output: 0

Explanation: An empty string has no substrings, so the answer is 0.

Input: "dvdf"

Expected Output: 3

Explanation: The best substring is "vdf", which has length 3.

Hints

Use a sliding window with two pointers to keep a valid substring.
Track the most recent index of each character so you can move the left boundary efficiently.

Part 2: Count Disjoint-Character String Pairs

Given a list of strings `words`, count the number of unique unordered pairs of indices `(i, j)` with `i < j` such that `words[i]` and `words[j]` share no common characters. Two strings share no common characters if there is no character that appears in both strings. Repeated letters inside the same word do not matter; only the set of distinct characters in each word matters. Additional assumption for this version: across the entire input, at most 20 distinct lowercase letters appear. This allows an exact bitmask dynamic programming solution in Python.

Constraints

0 <= len(words) <= 2 * 10^5
0 <= len(words[i]) <= 10^3
Each word contains only lowercase letters 'a' to 'z'
Across all words combined, at most 20 distinct characters appear
The result may be larger than 32-bit integer range

Examples

Input: ["apple", "banana", "peach", "kiwi"]

Expected Output: 3

Explanation: Valid pairs are ("apple", "kiwi"), ("banana", "kiwi"), and ("peach", "kiwi").

Input: ["ab", "cd", "a", "ef"]

Expected Output: 5

Explanation: Valid pairs are ("ab","cd"), ("ab","ef"), ("cd","a"), ("cd","ef"), and ("a","ef").

Input: []

Expected Output: 0

Explanation: With no words, there are no pairs.

Input: ["", "", "a"]

Expected Output: 3

Explanation: Both empty strings are disjoint with each other and with "a", so all 3 pairs are valid.

Input: ["ab", "ab", "cd"]

Expected Output: 2

Explanation: Each "ab" forms a valid pair with "cd", but the two "ab" strings are not disjoint.

Hints

Convert each word into a bitmask of the characters it contains. Two words are compatible exactly when their masks have bitwise AND equal to 0.
If `freq[mask]` is the number of words with an exact mask, a subset-sum DP can tell you how many words have masks that are subsets of a target complement mask.

Quick Overview

This question evaluates proficiency in string-processing algorithms, sliding-window techniques, efficient set or bitmask representations, and combinatorial pair counting under strict time and space constraints.