Partition Labels — Day 31(Python)

Image for post
Image for post
Photo by Alex on Unsplash

Today’s question is a frequent question among Amazon interviewers. Let jump into the problem without wasting much time.

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

  • S will have the length in the range [1, 500].
  • S will consist of lowercase English letters ('a' to 'z') only.

The question wants us to find partitions such that characters from one partition are absent in other partitions. One of the hints from the question we get is that we would need some data structure that can keep track of the last occurrence index of each character. We can use a dictionary to keep track of the last index. After creating a dictionary, go through each character in the string, check for its last occurrence. While traversing through the string, we need to keep the counter of the current index. If the current index is equal to the last occurrence previously visited, that means we have the partition point.

Let us look into the code.

import collections
class PartitionLabeller:
def partitionLabels(self, S: str) -> List[int]:
#holds last index
last = {c: i for i, c in enumerate(S)}
j = start = 0
ans = []
for i, c in enumerate(S):
j = max(j, last[c])
if i == j:
ans.append(i - start + 1)
start = i + 1
return ans

Complexity analysis.

Time Complexity

We are traversing through the list two times.

  1. When we are creating the last occurrence index of each character.
  2. When traversing through the String to find the partition point.

Hence the time complexity is O(N), where N is the length of the string.

Space Complexity

We are using a dictionary data structure to store the last occurrence index of each character. Hence space complexity is O(N), where N is the length of the string.

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store