Maximize partitions in a String

Given a string s of lowercase English alphabets, your task is to return the maximum number of substrings formed, after possible partitions (probably zero) of s such that no two substrings have a common character.

Examples:

Input: s = "acbbcc"
Output: 2
Explanation: "a" and "cbbcc" are two substrings that do not share any characters between them.

Input: s = "ababcbacadefegdehijhklij"
Output: 3
Explanation: Partitioning at the index 8 and at 15 produces three substrings: “ababcbaca”, “defegde”, and “hijhklij” such that none of them have a common character. So, the maximum number of substrings formed is 3.

Input: s = "aaa"
Output: 1
Explanation: Since the string consists of same characters, no further partition can be performed. Hence, the number of substring (here the whole string is considered as the substring) is 1.

Constraints:
1 ≤ s.size() ≤ 10⁵
‘a’ ≤ s[i] ≤ ‘z’ 

Approach 01:

#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

class Solution {
public:
    int maxPartitions(string s) {
        unordered_map<char, int> lastOccurrence;
        
        for (int i = 0; i < s.size(); ++i)
            lastOccurrence[s[i]] = i;
        
        int farthestIndex = -1;
        int partitionCount = 0;
        
        for (int i = 0; i < s.size(); ++i) {
            farthestIndex = max(farthestIndex, lastOccurrence[s[i]]);
            
            if (farthestIndex == i)
                ++partitionCount;
        }
        
        return partitionCount;
    }
};

class Solution:
    def maxPartitions(self, s: str) -> int:
        lastOccurrence = {char: index for index, char in enumerate(s)}
        
        farthestIndex = -1
        partitionCount = 0
        
        for index, char in enumerate(s):
            farthestIndex = max(farthestIndex, lastOccurrence[char])
            
            if farthestIndex == index:
                partitionCount += 1
                
        return partitionCount

Time Complexity:

• Recording Last Occurrences:

  Iterating through the string s to store the last occurrence of each character takes \( O(n) \), where \( n \) is the length of s.

• Determining Partitions:

  Another pass through s to determine partitions also takes \( O(n) \).

• Total Time Complexity:

  Since both operations run in \( O(n) \), the overall time complexity is \( O(n) \).

Space Complexity:

• Storing Last Occurrences:

  The unordered map lastOccurrence stores at most 26 key-value pairs (for lowercase letters), taking \( O(1) \) space.

• Auxiliary Variables:

  Integer variables like farthestIndex and partitionCount take \( O(1) \) space.

• Total Space Complexity:

  Since no additional space is used apart from the fixed-size map, the overall space complexity is \( O(1) \).