Welcome to Subscribe On Youtube

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

Solution 2: Dynamic Programming

Thinking

Enumerating every partition is exponential. The string length can reach $10^5$, and each digit is from $1$ to $9$, so whenever the current digit is at most $k$ the first call always lands on the next index and the chain has depth $n$. A piece cannot grow once its value exceeds $k$, so the fewest pieces from index $i$ depend only on later indices. Let $f[i]$ be that count, with $f[n]=0$, and fill $i$ from $n-1$ down to $0$: accumulate the substring value, update from each end that stays within $k$ using $f[j+1]$, then add one. If $f[0]$ is still at least the sentinel, return $-1$.

We let $f[i]$ be the minimum number of partitions starting from index $i$ of string $s$, with $f[n] = 0$. The answer is $f[0]$.

Scan $i$ from $n - 1$ down to $0$. Accumulate the integer value of the substring starting at $i$, and stop once it exceeds $k$. For each end $j$ whose value is at most $k$, update $f[i]$ with $f[j + 1]$, then add one to $f[i]$.

If $f[0]$ is at least the preset upper bound, there is no good partition and we return $-1$. Otherwise we return $f[0]$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the string $s$.

  • 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;
    }
}


// Solution 2
class Solution {
    public int minimumPartition(String s, int k) {
        int n = s.length();
        int inf = 1 << 30;
        int[] f = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            f[i] = inf;
        }
        for (int i = n - 1; i >= 0; --i) {
            long v = 0;
            for (int j = i; j < n; ++j) {
                v = v * 10 + (s.charAt(j) - '0');
                if (v > k) {
                    break;
                }
                f[i] = Math.min(f[i], f[j + 1]);
            }
            ++f[i];
        }
        return f[0] < inf ? f[0] : -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;
    }
};


// Solution 2
class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.size();
        const int inf = 1 << 30;
        vector<int> f(n + 1, inf);
        f[n] = 0;
        for (int i = n - 1; i >= 0; --i) {
            long long v = 0;
            for (int j = i; j < n; ++j) {
                v = v * 10 + (s[j] - '0');
                if (v > k) {
                    break;
                }
                f[i] = min(f[i], f[j + 1]);
            }
            ++f[i];
        }
        return f[0] < inf ? f[0] : -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



# Solution 2
class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        n = len(s)
        f = [inf] * (n + 1)
        f[n] = 0
        for i in range(n - 1, -1, -1):
            v = 0
            for j in range(i, n):
                v = v * 10 + int(s[j])
                if v > k:
                    break
                f[i] = min(f[i], f[j + 1])
            f[i] += 1
        return f[0] if f[0] < 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
}


// Solution 2
func minimumPartition(s string, k int) int {
	n := len(s)
	const inf = 1 << 30
	f := make([]int, n+1)
	for i := 0; i < n; i++ {
		f[i] = inf
	}
	for i := n - 1; i >= 0; i-- {
		v := 0
		for j := i; j < n; j++ {
			v = v*10 + int(s[j]-'0')
			if v > k {
				break
			}
			f[i] = min(f[i], f[j+1])
		}
		f[i]++
	}
	if f[0] < inf {
		return f[0]
	}
	return -1
}

All Problems

All Solutions