Welcome to Subscribe On Youtube

2707. Extra Characters in a String

Description

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

 

Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

 

Constraints:

  • 1 <= s.length <= 50
  • 1 <= dictionary.length <= 50
  • 1 <= dictionary[i].length <= 50
  • dictionary[i] and s consists of only lowercase English letters
  • dictionary contains distinct words

Solutions

  • class Solution {
        public int minExtraChar(String s, String[] dictionary) {
            Set<String> ss = new HashSet<>();
            for (String w : dictionary) {
                ss.add(w);
            }
            int n = s.length();
            int[] f = new int[n + 1];
            f[0] = 0;
            for (int i = 1; i <= n; ++i) {
                f[i] = f[i - 1] + 1;
                for (int j = 0; j < i; ++j) {
                    if (ss.contains(s.substring(j, i))) {
                        f[i] = Math.min(f[i], f[j]);
                    }
                }
            }
            return f[n];
        }
    }
    
  • class Solution {
    public:
        int minExtraChar(string s, vector<string>& dictionary) {
            unordered_set<string> ss(dictionary.begin(), dictionary.end());
            int n = s.size();
            int f[n + 1];
            f[0] = 0;
            for (int i = 1; i <= n; ++i) {
                f[i] = f[i - 1] + 1;
                for (int j = 0; j < i; ++j) {
                    if (ss.count(s.substr(j, i - j))) {
                        f[i] = min(f[i], f[j]);
                    }
                }
            }
            return f[n];
        }
    };
    
  • class Solution:
        def minExtraChar(self, s: str, dictionary: List[str]) -> int:
            ss = set(dictionary)
            n = len(s)
            f = [0] * (n + 1)
            for i in range(1, n + 1):
                f[i] = f[i - 1] + 1
                for j in range(i):
                    if s[j:i] in ss and f[j] < f[i]:
                        f[i] = f[j]
            return f[n]
    
    
  • func minExtraChar(s string, dictionary []string) int {
    	ss := map[string]bool{}
    	for _, w := range dictionary {
    		ss[w] = true
    	}
    	n := len(s)
    	f := make([]int, n+1)
    	for i := 1; i <= n; i++ {
    		f[i] = f[i-1] + 1
    		for j := 0; j < i; j++ {
    			if ss[s[j:i]] && f[j] < f[i] {
    				f[i] = f[j]
    			}
    		}
    	}
    	return f[n]
    }
    
  • function minExtraChar(s: string, dictionary: string[]): number {
        const ss = new Set(dictionary);
        const n = s.length;
        const f = new Array(n + 1).fill(0);
        for (let i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            for (let j = 0; j < i; ++j) {
                if (ss.has(s.substring(j, i))) {
                    f[i] = Math.min(f[i], f[j]);
                }
            }
        }
        return f[n];
    }
    
    
  • use std::collections::HashSet;
    
    impl Solution {
        #[allow(dead_code)]
        pub fn min_extra_char(s: String, dictionary: Vec<String>) -> i32 {
            let n = s.len();
            let mut set = dictionary
                .iter()
                .map(|s| s.into())
                .collect::<HashSet<String>>();
            let mut dp = vec![0; n + 1];
    
            // Initialize the dp vector
            dp[0] = 0;
    
            // Begin the actual dp process
            for i in 1..=n {
                dp[i] = dp[i - 1] + 1;
                for j in 0..i {
                    if set.contains(&s[j..i]) {
                        dp[i] = std::cmp::min(dp[i], dp[j]);
                    }
                }
            }
    
            dp[n]
        }
    }
    

All Problems

All Solutions