Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

describe

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcBacadefegdehijhklij" Output: [9, 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.Copy the code

Example 2:

Input: s = "eccbbbbdec"
Output: [10]
Copy the code

Note:

1 <= s.length <= 500
s consists of lowercase English letters.
Copy the code

parsing

A string s is given, and it is required to divide s into different partitions, so that each character can appear in only one partition as much as possible. Finally, a list containing the length of each partition is returned. Here’s the clever idea:

  • Use the dictionary D to record the last occurrence of different characters in string S
  • Then initialize both j and Anchor to 0
  • In the process of traversing S, each character and index are C and I. J is the furthest index of the characters that have appeared. If I == j, it means that all character types that appear before this position only appear in the current partition, at this point, the partition length can be calculated and added to result. And updates the anchor to the initial location of the new partition

answer

class Solution(object):
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        d = {c:i for i,c in enumerate(s)}
        j = anchor = 0
        result = []
        for i,c in enumerate(s):
            j = max(j, d[c])
            if i==j:
                result.append(i-anchor+1)
                anchor = i+1
        return result          	      
		
Copy the code

The results

Each node in the given list has linked to Partition Labels in the linked list. Given in Python online submissions for Partition Labels.Copy the code

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation