Solution Explanation

The problem asks to partition a string into sub-strings such that each character appears in at most one partition. The solution uses a greedy approach with a hash table (or array) to efficiently track the last occurrence of each character.

Algorithm:

1. Find Last Occurrences: Iterate through the input string s and store the index of the last occurrence of each character in a hash map (Python, Java, JavaScript) or an array (C++, Go, Rust, TypeScript, C#). This allows for O(1) lookup of the last index of any character.

2. Greedy Partitioning:

   • Initialize j (start index of current partition) to 0 and mx (the maximum last index encountered so far in the current partition) to 0.
   • Iterate through the string:
     • For each character, update mx to be the maximum of mx and the last occurrence of that character (obtained from the hash map/array).
     • If mx is equal to the current index i, it means that all characters within the current partition have been encountered, and this partition can be closed. Add i - j + 1 (the length of the current partition) to the result list ans and update j to i + 1 to start the next partition.

Time Complexity: O(n), where n is the length of the string. The algorithm iterates through the string twice: once to find the last occurrences of each character and once to perform the partitioning. Both iterations take linear time.

Space Complexity: O(1) in the average case (for hash map in Python, Java, JavaScript), or O(26) in the worst case because we store the last occurrence of 26 lowercase letters in an array (C++, Go, Rust, C#, TypeScript). The space complexity is constant because it only depends on the fixed number of characters in the alphabet. The space used by the result list is also proportional to the number of partitions, which is at most n (in the worst-case scenario of each character forming its own partition).

Code Explanation (using Python as a representative example):

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)} #Find last index of each char
        mx = j = 0
        ans = []
        for i, c in enumerate(s):
            mx = max(mx, last[c]) #Update maximum last index encountered
            if mx == i: #If all chars in current partition are seen
                ans.append(i - j + 1) #Add partition length
                j = i + 1 #Start next partition
        return ans

The code in other languages follows the same logic and algorithm, using appropriate data structures for their respective syntax. The key optimization is using a hash table or array to efficiently look up the last index of each character, enabling the linear-time complexity.