algorithm - C programming Problem - Maximum Partitions

Question

I'm struggling to solve and implement in C a function that gets as input a "string" which it contains the chars 'a' or 'b' (the input string might be included chars 'a' and 'b' altogether) , and what the function does is to divide the string to three parts each permutation/set without having NULL/empty chars at each permutation/set. the length of the permutation/set isn't necessarily equal, but they all (all the three parts of each set/permutation) have the same number of occurrence/appearance of chars 'a' . the function must return the maximum possibilities that we can divide the string by 3 at each possible set/permutation.

Examples: #1 input string: "ababa" is having 4 possibilities of permutations/sets (as I said each permutations is contains from 3 parts and if there's no 3 parts so this possibility is discarded ! ), in this case the maximum possibilities are: (ab,a,ba) , (a,bab,a) , (a,ba,ba) ,(ab,ab,a).

#2 input string: "bbbbb" is having 6 possibilities of permutations/sets (as I said each permutations is contains from 3 parts and if there's no 3 parts so this possibility is discarded ! ), in this case the maximum possibilities are: (be careful here 'a' is o has no occurance so at each permutation/set there's no 'a' and it's equal for each set -has no 'a'-) (bb,b,bb) , (bbb,b,b) , (bb,bb,b) ,(b,bbb,b),(b,bb,bb),(b,b,bbb).

#3 input string:'ababb' is having 0 possibilities, so the function returns empty string or NULL or " " even could return whatever we want which resemble about there's no possibilities for this string.

Im struggling to implement this function in C and Im stuck on it about three days. I started to think to solve this problem in recursive approach because we are talking about permutations and maximum possibilities. so I deeply thought and started with my algorithm as this: first condition is to check : 'a' % 3 == 0 for every 3 parts of one permutation/set . (set consists 3 parts ) and then to think what's the recursive rule for the other condition (the length of string > 3). but Im stuck and I couldn't complete I don't know how to continue, any help please? the hardest thing is to discover the recursive rule for my problem with its edge conditions.

Any help out?!

thanks alot.

Answer 1

With fixed number of parts and known number K of "a"'s in every part you need just:

find position of K-th "a" p1
find position of K+1-st "a" p2
find position of 2K-th "a" p3
find position of 2K+1-st "a" p4

Then make two for-loops - one (i index) goes from p1 position to p2-1, second (j index) goes from p3 position to p4-1, and output string parts limited by [0..i], [i+1..j], [j+1..strlen-1] indices.

Example in Python:

def makeparts(s):
    acnt = s.count('a')
    if acnt % 3:
        return #no solutions
    ca = 0
    ka = acnt // 3
    for i in range(len(s)):
        if s[i] == 'a':
            ca += 1
            if ca == ka:
                ip1 = i
            elif ca == ka + 1:
                ip2 = i
            if ca == 2 * ka:  #note separate "if"
                ip3 = i
            elif ca == 2 * ka + 1:
                ip4 = i
    for left in range(ip1, ip2):
        for right in range(ip3, ip4):
            print(s[:left + 1], s[left+1:right+1], s[right+1:])

makeparts('abbabbba')
makeparts('abbababbbababa')

a bba bbba
a bbab bba
a bbabb ba
a bbabbb a
ab ba bbba
ab bab bba
ab babb ba
ab babbb a
abb a bbba
abb ab bba
abb abb ba
abb abbb a

abba babbba baba
abba babbbab aba
abbab abbba baba
abbab abbbab aba