Greedy: Given a string, partition the string such that each letter appears at only one part

Problem Statement:

You are given a string, you need to partition in such a way that each letter appears at most one part.

Example:

Input str = "ababafgfgf"
Output: [5, 5]

Solution Explanation:

We will use greedy approach to solve the problem.

The solution requires dividing string into smaller portion where each letter appears at most in one partition

For that we will track the last occurrence of each character and use it to determine partition boundaries.

Take a vector and store the last index of each character.

Traverse the string again and keep track of the farthest last occurrence.

Use left pointer to track the last partition, when the current index matches the farthest last occurrence, make partition.

store each partition result and send the result at the end.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;


vector<int> solution(string s) 
{

    vector<int> last(26, 0);
    
    for (int i = 0; i < s.size(); i++) 
    {
        last[s[i] - 'a'] = i;
    }

    vector<int> result;
    int maxLast = 0, prevEnd = -1;

    for (int i = 0; i < s.size(); i++) 
    {
        maxLast = max(maxLast, last[s[i] - 'a']);

        if (i == maxLast) 
        {
            result.push_back(i - prevEnd);
            prevEnd = i;
        }
    }

    return result;
}

int main() 
{
	string str = "ababafgfgf";

    vector<int> result = solution(str);

    for (auto i : result)
    	cout <<i<<" ";
}

Output

5 5