Solve three interview coding problems

This interview report described three coding tasks:

1. Generate a run-length spoken sequence Start with s1 = "1". To build the next term, read the current string from left to right, group consecutive identical digits, and write each group as <count><digit>. For example, "1" -> "11" -> "21" -> "1211". Given an integer n, return the nth term of the sequence.

2. Count substrings that can be rearranged into a palindrome Given a list of lowercase strings, compute the answer for each string independently. For a single string s, count how many non-empty contiguous substrings can be rearranged, by swapping characters, into a palindrome. Example: for s = "aabb", the answer is 9.

3. Replace wildcards to satisfy a digit-sum constraint You are given a numeric string such as "08??840", a target sum 24, and the rule that each ? must be replaced by a digit from 0 to 8 inclusive. Return all possible completed strings whose digits sum to the target. For example, valid outputs for "08??840" with target sum 24 are:

   • "0804840"
   • "0813840"
   • "0822840"
   • "0840840"

Return the complete set of valid strings in any order.

Part 1: Generate a Run-Length Spoken Sequence

Start with s1 = "1". To create the next term, scan the current term from left to right, group consecutive equal digits, and write each group as <count><digit>. For example, "1" -> "11" -> "21" -> "1211". Given an integer n, return the nth term of this sequence.

Constraints

• 1 <= n <= 25
• The answer fits in memory.

Examples

Example 1

Input: 1
Output: "1"

Explanation: Edge case: the first term is the starting value itself.

Example 2

Input: 2
Output: "11"

Explanation: Read "1" as one 1.

Hints

1. Build the sequence iteratively from term 1 up to term n.
2. When converting one term into the next, count consecutive equal digits with a loop or two pointers.

Part 2: Count Substrings That Can Be Rearranged Into a Palindrome

You are given a list of lowercase strings. For each string independently, count how many non-empty contiguous substrings can be rearranged into a palindrome. A substring can be rearranged into a palindrome if and only if at most one character appears an odd number of times. Return the counts in the same order as the input strings.

Constraints

• 0 <= len(strings) <= 10^4
• 0 <= len(s) for each s in strings
• Sum of lengths of all strings <= 2 * 10^5
• Each string contains only characters 'a' to 'z'

Examples

Example 1

Input: ["aabb"]
Output: [9]

Explanation: There are 9 non-empty substrings of "aabb" that can be rearranged into a palindrome.

Example 2

Input: ["abc", "aaaa"]
Output: [3, 10]

Explanation: "abc" contributes only its three single-character substrings. Every non-empty substring of "aaaa" works, so its count is 10.

Hints

1. A multiset of characters can form a palindrome if at most one character has odd frequency.
2. Use a prefix parity bitmask: two prefixes define a valid substring when their masks are equal or differ by exactly one bit.

Part 3: Replace Wildcards to Match a Digit Sum

You are given a string pattern containing digits and the character '?'. Each '?' must be replaced by a digit from 0 to 8 inclusive. Return all completed strings whose total digit sum equals target. For deterministic testing, return the valid strings sorted in lexicographic order.

Constraints

• 0 <= len(pattern) <= 15
• pattern contains only characters '0' to '9' and '?'
• 0 <= target <= 9 * len(pattern)
• Each '?' may only be replaced with a digit from 0 to 8

Examples

Example 1

Input: ("08??840", 24)
Output: ["0804840", "0813840", "0822840", "0831840", "0840840"]

Explanation: The fixed digits sum to 20, so the two wildcards must add up to 4.

Example 2

Input: ("5?1", 7)
Output: ["511"]

Explanation: The fixed digits already sum to 6, so the wildcard must be 1.

Hints

1. First compute the sum of the fixed digits, then only distribute the remaining sum across the '?' positions.
2. Use backtracking, but prune branches when the remaining sum is too small or too large for the remaining wildcard slots.