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

• Java
• C++
• Python
• Go

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

All Problems

All Solutions