In this article, we have explored approaches to solve the maximum string partition problem (Partition Labels) efficiently.

Table of contents

1. Problem statement
2. Brute Force approach
3. Logic for Efficient Approach
4. Efficient Algorithm
5. Final code

This is similar to Leetcode problem 763. Partition Labels.

Problem Statement

Given a string of alphabets, partition the string in maximum number of parts such that each letter appears in only one part. Output the number of partition and size of partitions.

Sample Input :

S="abcadedfg"

Expected Output :

Total partitions = 4
Partition lengths = 4, 3, 1, 1

Brute Force approach

The idea of the Brute Force approach is to check all partitions. The steps are:

• Generate all partitions
• For each partition, check if each substring has distinct characters that are not present in other characters. This can be done in O(N) time for a substring of length N.

The Time Complexity will be O(2^N-1 N) as

• There are 2^N-1 possible partitions. Imagine there is a bit 0 or 1 between each character. 0 denotes no partition and 1 denotes partition. These combinations of bits can be generated using the bitwise representation of numbers from 0 to 2^N-1-1

Logic for Efficient Approach

Store last occurence of every letter in an different array because condition is only fulfilled when one letter is present in only one partition so we can use this array to know how many partitions are possible.

Example :

1.Input :abcdefga
Output :-
Total partitions = 1
Partition lengths = 8

// part = "abcdefga" . ( because a present in last position also, so can not divide)

2.Input : aabbccde
Output :-
Total partitions = 5
Partition lengths = 2, 2, 2, 1, 1,

// parts = "aa", "bb", "cc", "d", "e" .

3.Input : kartikkeyan
Output :-
Total partitions = 2
Partition lengths = 10, 1

// parts = "kartikkeya", "n" . ( because of a present in 10th and 2nd position, we did not divide it before 10th position because it will create two partitions with a present in both parts )

Efficient Algorithm

The steps of our Efficient Algorithm are:

1.Create an array of size 26 to store last occurence of every alphabet present in the string.
2.Create a list of type int to store the partition lenghts.
3.Initialize three variables part_start, part_length and count as 0.
4.Run a loop through the string and change part_length to the last occurence of the alphabet present in that part of string.
5.When i equals to part_length it indicates all alphabets last occurences before that point is present in that part only so we can now partition from here.
6.Now Store length of partition in list and part_start now is equal to part_length + 1 so that we can count the exact length of next partition.
7.Increment count variable everytime when i==part_length to count number of partitions.
8.Output count and list elements.

Example :-

Input string : "ababc"
last occurence of 'a' = 2
last occurence of 'b' = 3
last occurence of 'c' = 4
part_length = 0
part_start = 0
count = 0

Iteration 1:
"ababc"
i=0
part_length = max(part_length, last occurence of 'a') = max(0,2) = 2

Iteration 2:
"ababc"
i=1
part_length = max(part_length, last occurence of 'b') = max(2,3) = 3

Iteration 3:
"ababc"
i=2
part_length = max(part_length, last occurence of 'a') = max(3,2) = 3

Iteration 4:
"ababc"
i=3
part_length = max(part_length, last occurence of 'b') = max(3,3) = 3
now, (i==part_length)
so,
list.push_back(3-0+1)
//add to list the partition size
part_start = part_length+1 = 3+1
// bring start position to ith value
count++
//number of partitions

Iteration 4:
"ababc"
i=4
part_length = max(part_length, last occurence of 'c') = max(3,4) = 4
(i==part_length)
so,
list.push_back(4-4+1)
part_start = part_length+1 = 4+1
count++

Output :-
Number of partitions = count = 2
List = [4,1]

Space Complexity :

O(1) , constant time as we are using an array of size 26*4=104 bytes and an list of type int.

Time Complexity :

O(n) , linear time because we are using two loops (not nested loops) where n = string length which is variable input.

Final Implementation in C++

   #include<bits/stdc++.h>
   using namespace std;

   int main()
   {   
      string s;
      cin>>s;
      int last[26];
      for(int i=0;i<s.length();i++)
      {   
          // To convert character into a numeric value 
          // subtract it by 'a'
          last[s[i]-'a']=i;
      }
      list<int> output;
      int part_start=0;          //start of partition
      int part_length=0;         //end of partition
      int count=0;               //number of partitions
      
      for(int i=0;i<s.length();i++)
      {
        part_length=max(part_length,last[s[i]-'a']);
        if(i==part_length)
        {
         output.push_back(part_length-part_start+1);
         part_start=i+1;
         count++;
        }
      }

      cout<<"Total partitions = "<<count<<"\n";
      cout<<"Partition lengths = ";
      for(auto i:output)             
      //syntax for 'foreach' loop
      cout << i << ", ";             
      //auto keyword automatically identifies the datatype

      return 0;
   }

With this article at OpenGenus, you must have the complete idea of Maximum String Partition problem: Partition Labels.