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 TikTok.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at TikTok during technical interviews.

Find second-minimal word segmentation count

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find second-minimal word segmentation count states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: TikTok

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a string s and a dictionary D of non-empty words, define a 'segmentation' as splitting s into a sequence of words from D whose concatenation equals s. Let the cost of a segmentation be the number of words used. Return the second-smallest possible cost among all valid segmentations, or -1 if fewer than two valid segmentations exist. Only return the cost; do not enumerate segmentations. Describe your algorithm, justify its time and space complexity, and explain how you would handle large inputs.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find second-minimal word segmentation count states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a string `s` and a dictionary `D` of non-empty words, a *segmentation* splits `s` into a sequence of words from `D` whose concatenation equals `s`. The **cost** of a segmentation is the number of words it uses. Return the **second-smallest possible cost** among all valid segmentations of `s`. If two different segmentations have the same cost, that cost is counted once per segmentation (i.e. consider the multiset of costs over all valid segmentations and return the value at the second position when sorted ascending). Return `-1` if fewer than two valid segmentations exist. Return only the cost — do not enumerate the segmentations. **Examples** - `s = "catsanddog"`, `D = ["cat","cats","and","sand","dog"]` → `3`. The two valid segmentations are `cats|and|dog` (cost 3) and `cat|sand|dog` (cost 3); the sorted multiset of costs is `[3, 3]`, so the second-smallest is `3`. - `s = "aaa"`, `D = ["a","aa"]` → `2`. Segmentations: `a|aa` (2), `aa|a` (2), `a|a|a` (3); sorted costs `[2, 2, 3]`, second-smallest is `2`. - `s = "leetcode"`, `D = ["leet","code"]` → `-1`. Only one valid segmentation exists. The word dictionary is passed as a list `words`; a word may be reused any number of times.

Constraints

1 <= len(s) <= 10^4 (s may also be empty, in which case the answer is -1).
Each word in the dictionary is non-empty.
Words may be reused any number of times within a segmentation.
Return -1 when fewer than two valid segmentations exist.

Examples

Input: ("catsanddog", ["cat", "cats", "and", "sand", "dog"])

Expected Output: 3

Explanation: Segmentations cats|and|dog (3) and cat|sand|dog (3); sorted costs [3,3] → second-smallest 3.

Input: ("aaaa", ["a", "aa", "aaa"])

Expected Output: 2

Explanation: Multiple cost-2 segmentations exist (e.g. aa|aa, a|aaa); the second position of the sorted cost multiset is 2.

Input: ("leetcode", ["leet", "code"])

Expected Output: -1

Explanation: Only one valid segmentation (leet|code), so there is no second-smallest cost.

Input: ("", ["a"])

Expected Output: -1

Explanation: Empty string has zero valid non-empty-word segmentations; fewer than two exist → -1.

Input: ("abcd", ["x", "y"])

Expected Output: -1

Explanation: No word matches any prefix; zero valid segmentations → -1.

Input: ("aaa", ["a", "aa"])

Expected Output: 2

Explanation: Segmentations a|aa (2), aa|a (2), a|a|a (3); sorted costs [2,2,3] → second-smallest 2.

Input: ("pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"])

Expected Output: 3

Hints

This is a variant of Word Break II, but you must NOT enumerate segmentations — track only the best two costs per prefix.
Let dp[i] hold the two smallest costs to segment the prefix s[0:i]. To extend, for every word ending at i, add 1 to each of the predecessor's two best costs and keep the global two smallest.
Keep a separate ways[i] counter (number of valid segmentations of s[0:i]) so you can correctly return -1 when fewer than two full segmentations exist — even if the two best costs happen to be equal.
Because costs are positive and additive, keeping only the two smallest per node is sufficient: the second-smallest full-string cost always extends one of the two smallest predecessor costs.

Quick Overview