Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2522.html

2522. Partition String Into Substrings With Values at Most K

Description

You are given a string s consisting of digits from 1 to 9 and an integer k.

A partition of a string s is called good if:

  • Each digit of s is part of exactly one substring.
  • The value of each substring is less than or equal to k.

Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.

Note that:

  • The value of a string is its result when interpreted as an integer. For example, the value of "123" is 123 and the value of "1" is 1.
  • A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "165462", k = 60
Output: 4
Explanation: We can partition the string into substrings "16", "54", "6", and "2". Each substring has a value less than or equal to k = 60.
It can be shown that we cannot partition the string into less than 4 substrings.

Example 2:

Input: s = "238182", k = 5
Output: -1
Explanation: There is no good partition for this string.

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is a digit from '1' to '9'.
  • 1 <= k <= 109

 

Solutions

  • class Solution {
        private Integer[] f;
        private int n;
        private String s;
        private int k;
        private int inf = 1 << 30;
    
        public int minimumPartition(String s, int k) {
            n = s.length();
            f = new Integer[n];
            this.s = s;
            this.k = k;
            int ans = dfs(0);
            return ans < inf ? ans : -1;
        }
    
        private int dfs(int i) {
            if (i >= n) {
                return 0;
            }
            if (f[i] != null) {
                return f[i];
            }
            int res = inf;
            long v = 0;
            for (int j = i; j < n; ++j) {
                v = v * 10 + (s.charAt(j) - '0');
                if (v > k) {
                    break;
                }
                res = Math.min(res, dfs(j + 1));
            }
            return f[i] = res + 1;
        }
    }
    
  • class Solution {
    public:
        int minimumPartition(string s, int k) {
            int n = s.size();
            int f[n];
            memset(f, 0, sizeof f);
            const int inf = 1 << 30;
            function<int(int)> dfs = [&](int i) -> int {
                if (i >= n) return 0;
                if (f[i]) return f[i];
                int res = inf;
                long v = 0;
                for (int j = i; j < n; ++j) {
                    v = v * 10 + (s[j] - '0');
                    if (v > k) break;
                    res = min(res, dfs(j + 1));
                }
                return f[i] = res + 1;
            };
            int ans = dfs(0);
            return ans < inf ? ans : -1;
        }
    };
    
  • class Solution:
        def minimumPartition(self, s: str, k: int) -> int:
            @cache
            def dfs(i):
                if i >= n:
                    return 0
                res, v = inf, 0
                for j in range(i, n):
                    v = v * 10 + int(s[j])
                    if v > k:
                        break
                    res = min(res, dfs(j + 1))
                return res + 1
    
            n = len(s)
            ans = dfs(0)
            return ans if ans < inf else -1
    
    
  • func minimumPartition(s string, k int) int {
    	n := len(s)
    	f := make([]int, n)
    	const inf int = 1 << 30
    	var dfs func(int) int
    	dfs = func(i int) int {
    		if i >= n {
    			return 0
    		}
    		if f[i] > 0 {
    			return f[i]
    		}
    		res, v := inf, 0
    		for j := i; j < n; j++ {
    			v = v*10 + int(s[j]-'0')
    			if v > k {
    				break
    			}
    			res = min(res, dfs(j+1))
    		}
    		f[i] = res + 1
    		return f[i]
    	}
    	ans := dfs(0)
    	if ans < inf {
    		return ans
    	}
    	return -1
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions