Package g2501_2600.s2522_partition_string_into_substrings_with_values_at_most_k

Class Solution

java.lang.Object

g2501_2600.s2522_partition_string_into_substrings_with_values_at_most_k.Solution

public class Solution
extends Object

2522 - Partition String Into Substrings With Values at Most K.<p>Medium</p> <p>You are given a string <code>s</code> consisting of digits from <code>1</code> to <code>9</code> and an integer <code>k</code>.</p> <p>A partition of a string <code>s</code> is called <strong>good</strong> if:</p> <ul> <li>Each digit of <code>s</code> is part of <strong>exactly</strong> one substring.</li> <li>The value of each substring is less than or equal to <code>k</code>.</li> </ul> <p>Return <em>the <strong>minimum</strong> number of substrings in a <strong>good</strong> partition of</em> <code>s</code>. If no <strong>good</strong> partition of <code>s</code> exists, return <code>-1</code>.</p> <p><strong>Note</strong> that:</p> <ul> <li>The <strong>value</strong> of a string is its result when interpreted as an integer. For example, the value of <code>&quot;123&quot;</code> is <code>123</code> and the value of <code>&quot;1&quot;</code> is <code>1</code>.</li> <li>A <strong>substring</strong> is a contiguous sequence of characters within a string.</li> </ul> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> s = &ldquo;165462&rdquo;, k = 60</p> <p><strong>Output:</strong> 4</p> <p><strong>Explanation:</strong> We can partition the string into substrings &ldquo;16&rdquo;, &ldquo;54&rdquo;, &ldquo;6&rdquo;, and &ldquo;2&rdquo;. 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.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> s = &ldquo;238182&rdquo;, k = 5</p> <p><strong>Output:</strong> -1</p> <p><strong>Explanation:</strong> There is no good partition for this string.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= s.length <= 10⁵</code></li> <li><code>s[i]</code> is a digit from <code>'1'</code> to <code>'9'</code>.</li> <li><code>1 <= k <= 10⁹</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minimumPartition(String s, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minimumPartition

public int minimumPartition(String s,
 int k)