<p>Given a string <code>s</code>, partition the string into one or more <strong>substrings</strong> such that the characters in each substring are <strong>unique</strong>. That is, no letter appears in a single substring more than <strong>once</strong>.</p>

<p>Return <em>the <strong>minimum</strong> number of substrings in such a partition.</em></p>

<p>Note that each character should belong to exactly one substring in a partition.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abacaba&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong>
Two possible partitions are (&quot;a&quot;,&quot;ba&quot;,&quot;cab&quot;,&quot;a&quot;) and (&quot;ab&quot;,&quot;a&quot;,&quot;ca&quot;,&quot;ba&quot;).
It can be shown that 4 is the minimum number of substrings needed.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ssssss&quot;
<strong>Output:</strong> 6
<strong>Explanation:
</strong>The only valid partition is (&quot;s&quot;,&quot;s&quot;,&quot;s&quot;,&quot;s&quot;,&quot;s&quot;,&quot;s&quot;).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only English lowercase letters.</li>
</ul>

/*
Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

s = abacaba
idx = 4
letters = [26 * false] = {"a" : true, "b" : false, "c" : false}
letters = 0
partitions = 4

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

s = abacaba
idx = 0

dp = [1, ]


Observations:
Two max possible partitions if you use the string s and reverse the string s.

Approach:

Approach #1: Greedy.
Initialize number of partitions to 1.
Iterate through string.
    Keep unsigned int mask.
    If character at mask bit exists, then increment partition and reset mask.
Do same operation reversed.
Return min of both sets of partitions.

*/
class Solution {
public:
    bool checkLettersMask(int mask, int c) {
        return mask & (1 << (c - 'a'));
    }
    int updateLettersMask(int mask, int c) {
        return mask | (1 << (c - 'a'));
    }
    int partitionStringOp(string s) {
        int partitions = 1;
        int mask = 0;
        for (int i=0;i<s.size();i++) {
            if (checkLettersMask(mask, s[i])) {
                partitions++;
                mask = 0;
            }
            mask = updateLettersMask(mask, s[i]);
        }
        return partitions;
    }
    int partitionString(string s) {
        string r = s;
        reverse(r.begin(), r.end());
        return min(partitionStringOp(s), partitionStringOp(r));   
    }
};
14361