Partition labels
August 10, 2022
greedyProblem URL: Partition labels
We will first count the last position of all chacracter in a hashmap. Then we will iterate through the string, check if the last index of the chacracter is equal to the current index, if yes, then we append the current length to our result. We will repeat this till the end of the string and then return the result.
class Solution:
def partitionLabels(self, s: str) -> List[int]:
res = []
count = {}
i, length = 0, len(s)
for j in range(length):
count[s[j]] = j
curLen = 0
goal = 0
while i < length:
c = s[i]
goal = max(goal, count[c])
curLen += 1
if goal == i:
res.append(curLen)
curLen = 0
i += 1
return res
Time Complexity: O(n)
Space Complexity: O(1)