Minimum Leftover Characters (Medium) — Practice with Code Visualizer

You are given a string s and an array of valid words called wordBank. Your task is to segment the string s into non-overlapping substrings where each substring must exist in the wordBank. Some characters in s may not be covered by any valid word and will remain as "leftover" characters.

Your goal is to determine the minimum number of leftover characters that cannot be matched by any word from the wordBank when you segment s optimally.

Key Observations:

Words from the wordBank must appear as contiguous substrings in s.
The same word can be used multiple times if it appears at different positions.
Substrings selected from s cannot overlap with each other.
Any character in s that is not part of a selected matching substring is considered a leftover character.

This is a classic string segmentation problem that requires finding the optimal way to cover as many characters as possible using the available words, thereby minimizing the characters that are left uncovered.

We can segment the string optimally as "leet" (indices 0-3) and "code" (indices 5-8). The character 's' at index 4 cannot be matched by any word in the wordBank, so there is 1 leftover character.

We can match "hello" (indices 3-7) and "world" (indices 8-12). The characters 's', 'a', 'y' at indices 0, 1, 2 are not covered by any word. Hence, 3 characters are leftover.

The entire string can be perfectly segmented as "apple" (indices 0-4) and "pie" (indices 5-7). Every character is covered by a valid word, resulting in 0 leftover characters.