> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 2522. Partition String Into Substrings With Values at Most K
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-9/
- Published: 2023-01-01T07:44:05.000Z
- Updated: 2026-11-07T18:26:15.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> 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:

```vbnet
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:

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

Constraints:

1. `1 <= s.length <= 10^5`
2. `s[i]` is a digit from `'1'` to `'9'`.
3. `1 <= k <= 10^9`

### 效能

- Time complexity: `O(n)`
- Space complexity: `O(n)`
- Runtime: 145 ms
- Memory: 52 MB

---

### 題解

Weekly Contest 326，Medium。

給定一組字串和一個指定的數字，將指定的數字當作上限，把字串分割成小於指定數字的子字串，回傳子字串數量。

```kotlin
var s = "165462"; 
var k = 60; 
 
// 可以分割成：[16, 54, 6, 2] 
return 4;
```

如果有超過指定數字的子字串，回傳 `-1`：

```kotlin
var s = "238182"; 
var k = 5; 
 
// 8 > 5 
return -1;
```

---

### 滑動視窗

這題給我的感覺滿像滑動視窗的，都需要找一個區間出來做比較，超過就做一些處理。重點會放在：

1. 定義視窗區間的開始和結束
2. 超過時要如何重製區間的開始和結束

嘗試過用 `startIndex` 和 `endIndex` 來理解這個題目，搭配 `s.Substring()` 來找出區間，但在邏輯上對於區間總和超過 `k` 時，要如何重製 `startIndex` 和 `endIndex` 有點混亂。

但其實這題不需要特別指定 `startIndex` 和 `endIndex` 也可以達成：

```kotlin
// 區間 
var substring = ""; 
 
// for 迴圈不包括最後一個區間 
var result = 1; 
 
foreach (var item in s) 
{ 
    // char 可以被轉換成 ASCII Code 做計算 
    // 以 Examplet 2 為例 
    // k = 5，如果 item > k(5) 就代表超過指定數字 
    // 回傳 -1 
    if (item - '0' > k) return -1; 
 
    // 把數字加入新的區間 
    substring += item; 
 
    // 要注意測資的指定大小來決定 Convert 的目標 
    if (Convert.ToDouble(substring) > k) 
    { 
        // 如果區間的數字大於 k 
        // 代表在這之前的區間是合法的子字串 
        result++; 
         
        // 更新區間為目前的數字 
        substring = item.ToString(); 
    } 
} 
 
return result;
```

---

#### 參考資料

- [2522\. Partition String Into Substrings With Values at Most K](https://leetcode.com/problems/partition-string-into-substrings-with-values-at-most-k/description/?ref=blog.anthea.day)
- [2522\. Partition String Into Substrings With Values at Most K — Solutions: C# O(N)](https://leetcode.com/problems/partition-string-into-substrings-with-values-at-most-k/solutions/2977545/c-o-n/?ref=blog.anthea.day)