2522. Partition String Into Substrings With Values at Most K LeetCode Solution

In this guide, you will get 2522. Partition String Into Substrings With Values at Most K LeetCode Solution with the best time and space complexity. The solution to Partition String Into Substrings With Values at Most K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Partition String Into Substrings With Values at Most K solution in C++
4. Partition String Into Substrings With Values at Most K solution in Java
5. Partition String Into Substrings With Values at Most K solution in Python
6. Additional Resources

Problem Statement of Partition String Into Substrings With Values at Most K

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

2522. Partition String Into Substrings With Values at Most K LeetCode Solution in C++

class Solution {
 public:
  int minimumPartition(string s, int k) {
    int ans = 1;
    long curr = 0;

    for (const char c : s) {
      curr = curr * 10 + c - '0';
      if (curr > k) {
        curr = c - '0';
        ++ans;
      }
      if (curr > k)
        return -1;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2522. Partition String Into Substrings With Values at Most K LeetCode Solution in Java

class Solution {
  public int minimumPartition(String s, int k) {
    int ans = 1;
    long curr = 0;

    for (final char c : s.toCharArray()) {
      curr = curr * 10 + c - '0';
      if (curr > k) {
        curr = c - '0';
        ++ans;
      }
      if (curr > k)
        return -1;
    }

    return ans;
  }
}
// code provided by PROGIEZ

2522. Partition String Into Substrings With Values at Most K LeetCode Solution in Python

class Solution:
  def minimumPartition(self, s: str, k: int) -> int:
    ans = 1
    curr = 0

    for c in s:
      curr = curr * 10 + int(c)
      if curr > k:
        curr = int(c)
        ans += 1
      if curr > k:
        return -1

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.