Optimal Partition of String

Greedy Algorithm, Hash Table.

Original Link

Solution

In this problem, we should find the minimum possible partitions that can divide the input string into multiple(or single) substring(s). The same character should not be in each substring.

We should create a substring containing as many characters as possible. Otherwise, we might need more partitions to split the duplicated characters. Thus, a greedy algorithm simply works here.

class Solution {
public:
    int partitionString(string s) {
        int n = (int)s.size();
        int ans = 1;
        vector<int> cnt(26, 0);
        for (int i = 0; i < n; ++i) {
            if (cnt[s[i]-'a'] == 1) {
                ++ans;
                fill(cnt.begin(), cnt.end(), 0);
            }
            cnt[s[i]-'a']++;
        }
        return ans;
    }
};

Then, why does the greedy algorithm work here?

Let’s say that we get the answer without using a greedy algorithm. There are two partitions: A and B.

• A partition can contain more characters in the B partitions. If not, then we already solved it with a greedy algorithm.

• A partition can contain some characters or all characters in the B partitions. It means that a greedy solution gets the same or fewer partitions. So, the greedy algorithm works here.