Solve four coding problems

The interview included four independent coding problems:

1. Longest all-healthy service streak You are given the daily health-check results for multiple microservices. Each day is considered healthy only if every microservice passed its health check on that day. Find the maximum number of consecutive healthy days.

2. Shortest substring covering all distinct characters You are given a string s. Find the length of the shortest substring that contains every distinct character that appears anywhere in s at least once.

3. Minimize remaining product types after deletions You are given a list of product IDs and an integer m. In one operation, you may delete one occurrence of any product ID. After performing exactly m deletions, minimize the number of distinct product IDs that remain. Return that minimum number.

4. Count string pairs that can form a palindrome You are given an array of strings. Count how many pairs of strings (i, j) with i < j have the property that, after combining all characters from both strings and reordering them arbitrarily, the result can form a palindrome.

Part 1: Longest All-Healthy Service Streak

You are given a 2D list results where results[d][s] is 1 if microservice s passed its health check on day d, and 0 otherwise. A day is considered healthy only if every microservice passed on that day. Return the maximum number of consecutive healthy days.

Constraints

• 0 <= len(results) <= 100000
• If results is non-empty, each day contains the same number of services and at least 1 service
• Each value is either 0 or 1

Examples

Example 1

Input: ([[1,1,1],[1,1,1],[1,0,1],[1,1,1],[1,1,1],[1,1,1]],)
Output: 3

Explanation: The first two days are healthy, the third day breaks the streak, and the last three days form the longest healthy streak.

Example 2

Input: ([[1,0],[0,1]],)
Output: 0

Explanation: No day has all services passing.

Hints

1. First decide for each day whether it is healthy or not.
2. Then scan the days and track the longest consecutive run of healthy ones.

Part 2: Shortest Substring Covering All Distinct Characters

You are given a string s. Find the length of the shortest substring that contains every distinct character that appears anywhere in s at least once. If s is empty, return 0.

Constraints

• 0 <= len(s) <= 200000
• Characters may repeat arbitrarily
• The solution should be efficient for long strings

Examples

Example 1

Input: ("aabcbcdbca",)
Output: 4

Explanation: The distinct characters are a, b, c, and d. The shortest substring containing all of them is "dbca".

Example 2

Input: ("aaaa",)
Output: 1

Explanation: There is only one distinct character, so any single 'a' works.

Hints

1. Count how many unique characters exist in the whole string first.
2. A sliding window can expand to satisfy the requirement and shrink to find the minimum length.

Part 3: Minimize Remaining Product Types After Deletions

You are given a list of product IDs and an integer m. In one operation, you may delete one occurrence of any product ID. After performing exactly m deletions, minimize the number of distinct product IDs that remain. Return that minimum number.

Constraints

• 0 <= len(product_ids) <= 200000
• 0 <= m <= len(product_ids)
• Product IDs are integers

Examples

Example 1

Input: ([1,1,1,2,2,3], 3)
Output: 1

Explanation: Delete product 3 once and product 2 twice. Only product 1 remains.

Example 2

Input: ([4,3,1,1,3,3,2], 3)
Output: 2

Explanation: The best choice is to remove the two IDs with frequency 1, then one extra deletion cannot remove another ID completely.

Hints

1. A distinct ID disappears only when all of its occurrences are deleted.
2. To remove the most distinct IDs, eliminate the IDs with the smallest frequencies first.

Part 4: Count String Pairs That Can Form a Palindrome

You are given an array words of lowercase English strings. Count how many pairs (i, j) with i < j have the property that after combining all characters from words[i] and words[j] and reordering them arbitrarily, the result can form a palindrome.

Constraints

• 0 <= len(words) <= 200000
• 0 <= sum(len(word) for word in words) <= 200000
• Each string contains only lowercase English letters 'a' to 'z'

Examples

Example 1

Input: (["abc","cba","xy","yx"],)
Output: 2

Explanation: The valid pairs are ("abc", "cba") and ("xy", "yx").

Example 2

Input: (["a","","bb","ab"],)
Output: 4

Explanation: The valid pairs are ("a", ""), ("a", "bb"), ("a", "ab"), and ("", "bb").

Hints

1. A multiset of characters can be rearranged into a palindrome if at most one character has an odd count.
2. For each string, track only which letters have odd frequency, using a bitmask.