SplitSentense.cpp

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
using namespace std;

vector<int> SplitsSentense(string s)
{
	vector<int> width_string_parts;
	int length = s.length();

	//For conventional array use this 
	int arr[26];
	std::fill_n(arr, 26, -1);

	//Another way can be for std::array
	std::array<int, 26> another_arr;
	another_arr.fill(-1);

	for (int index = length - 1; index >= 0; --index)
	{

		if (arr[s[index] - 'a'] == -1)
		{
			arr[s[index] - 'a'] = index; //Last occurance of this char found at some index x
		}
	}

	int part_start = 0;
	int index = 0;
	int prev_depend_index = -1;

	while (index < length)
	{
		//is this is last occurance of this char
		if (arr[s[index] - 'a'] <= index) //it cna be a split point
		{
			if (prev_depend_index <= index)
			{
				width_string_parts.push_back(index - part_start + 1);
				prev_depend_index = -1;
				part_start = index + 1;
			}
		}

		if (prev_depend_index < arr[s[index] - 'a'])
		{
			prev_depend_index = arr[s[index] - 'a'];
		}
		index++;
	}
	return width_string_parts;
}

int main()
{
	string s("ababcbacadefegdehijhklij");
	vector<int> v = SplitsSentense(s);
	for(auto x : v)
	{
		cout << x << "  ";
	}
    return 0;
}