Untitled

import java.util.*;

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(dictionary)); // Use a set for fast lookups
        return partitionAndSolve(s, 0, wordSet, new Integer[s.length()]);
    }

    private int partitionAndSolve(String s, int start, Set<String> wordSet, Integer[] memo) {
        // Base case: If we've reached the end of the string, no extra characters remain.
        if (start == s.length()) return 0;

        // Check memoized results.
        if (memo[start] != null) return memo[start];

        // Initialize the minimum extra characters to the worst case: all remaining characters are extra.
        int minExtra = s.length() - start;

        // Try partitioning the string into segments of all possible lengths starting at 'start'.
        for (int end = start + 1; end <= s.length(); end++) {
            String segment = s.substring(start, end);

            // Check if the segment exists in the dictionary.
            if (wordSet.contains(segment)) {
                // If it does, move to the next state without adding extra characters.
                minExtra = Math.min(minExtra, partitionAndSolve(s, end, wordSet, memo));
            } else {
                // If it doesn't, count its length as extra and move to the next state.
                minExtra = Math.min(minExtra, segment.length() + partitionAndSolve(s, end, wordSet, memo));
            }
        }

        // Memoize and return the result.
        memo[start] = minExtra;
        return minExtra;
    }
}