파비의 매일매일 공부기록

2023.04.04 Today's Challenge 본문

Problem Solving/LeetCode

2023.04.04 Today's Challenge

fabichoi 2023. 4. 4. 23:45

https://leetcode.com/problems/optimal-partition-of-string/

 

Optimal Partition of String - LeetCode

Can you solve this real interview question? Optimal Partition of String - Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than o

leetcode.com

탐욕법으로 풀면 되는 문제!

class Solution:
    def partitionString(self, s: str) -> int:
        ls = [-1] * 26
        cnt = 1
        ss = 0

        for i in range(len(s)):
            if ls[ord(s[i]) - ord('a')] >= ss:
                cnt += 1
                ss = i
            ls[ord(s[i]) - ord('a')] = i
        
        return cnt
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.04.06 Today's Challenge  (0) 2023.04.06
2023.04.05 Today's Challenge  (0) 2023.04.05
2023.04.03 Today's Challenge  (0) 2023.04.03
2023.04.02 Today's Challenge  (0) 2023.04.02
2023.04.01 Today's Challenge  (0) 2023.04.01
'Problem Solving/LeetCode' Related Articles more
Comments