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

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

LeetCode 2522번 문제를 풀어보았다.. Link

Problem

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.

Intuition

Two pointer approach로 포인터들을 적절하게 움직이며 Good partition인지 아닌지 판별한다면 풀 수 있는 문제라고 생각된다.

별다른 자료구조가 필요한건 아닌거 같으니 구현만 잘 하면 될 듯?

Approach

1. start와 end는 정수로 된 문자열을 쪼개기 위한 포인터로, 각각 0과 1로 초기화

2. result는 partition 개수를 기록하기 위한 변수로 0으로 초기화

3. 문자열 s[start:end]가 k보다 작거나 같으면 end += 1을 한다. (substring의 길이를 늘린다. 최소 파티션을 구하는 거니까)

4. s[start:end]가 k보다 클 때

   1. start=end-1 (일의 자리 수)라면 -1을 반환한다.
   2. 그게 아니라면 result += 1을 하고, start 지점을 end-1로 옮긴다.

5. end가 len(s) + 1보다 작을동안 반복한다.

6. result + 1을 반환한다. (result에는 몇번 나눌지에 대한 숫자가 들어간것이기 때문에 실제 파티션 개수는 +1이 되어야 함)

Complexity

• Time complexity:

  \[O(n)\]

• Space complexity: \(O(1)\)

My Code

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        start = 0
        end = 1
        result = 0
        while end < len(s)+1:
            #print(start, end, s[start:end])
            if int(s[start:end]) <= k:
                end += 1
            else:
                if start == end-1:
                    return -1
                result += 1
                start = end - 1
            
        return result + 1