Given a String, What is the Length of the One of the Longest WFF in Polish Notation?

Question

I'm trying to write a version of always popular Count-A-WFF section of the WFF 'N Proof game (no copyright infringement intended) in Python. Alright, not so popular.

I think I have everything up and running up as desired for up to the case of a 4 letter string.

def maximum_string(s):
if cs(s) == True:
    return len(s)
elif len(s) == 2:
    l1 = [cs(s[0]), cs(s[1])]
    if True in l1:
        return len(s) - 1
    else:
        return 0
elif len(s) == 3:
    first = s[0] + s[1]
    second = s[0] + s[2]
    third = s[1] + s[2]
    l1 = [cs(first), cs(second), cs(third)]
    if True in l1:
        return len(s) - 1
    l2 = [cs(s[0]), cs(s[1]), cs(s[2])]
    if True in l2:
        return len(s) - 2
    else:
        return 0
elif len(s) == 4:
    first = s[0]+s[1]+s[2]
    second = s[0]+s[1]+s[3]
    third = s[1]+s[2]+s[3]
    fourth = s[0]+s[2]+s[3]
    l1 = [cs(first), cs(second), cs(third), cs(fourth)]
    if True in l1:
        return 3
    first = s[0] + s[1]
    second = s[0] + s[2]
    third = s[0] + s[3]
    fourth = s[1] + s[2]
    fifth = s[1] + s[3]
    sixth = s[2] + s[3]
    l2 = [cs(first), cs(second), cs(third), cs(fourth), cs(fifth), cs(sixth)]
    if True in l2:
        return 2
    first = s[0]
    second = s[1]
    third = s[2]
    fourth = s[3]
    l3 = [cs(first), cs(second), cs(third), cs(fourth)]
    if True in l3:
        return 1
    else:
        return 0

def cs(string):
global length_counter, counter, letter
counter = 1
length_counter = 0
letters_left = len(string)
while letters_left != 0 and length_counter < len(string):
    letter = string[length_counter]
    if letter == 'C' or letter == 'A' or letter == 'K' or letter == 'E' or letter == "K":
        counter += 1 
    elif letter == 'N':
        counter += 0
    else:
        counter -= 1  
    length_counter += 1
    letters_left -= 1
if counter == 0 and len(string) == length_counter:
    return True
else:
    return False

The maximum_string helper function is intended to, given any string S, find the length of one of the longest possible wffs that you can make from just the letters of S. Of course, I can continue the pattern I currently have for the maximum_string helper function up to a length of 13. But, combinatorial explosion is evident. Thus, is there a more elegant way to finish off the maximum string helper function?

Answer 1

In effect one of the functions I had earlier would return a distance of how far away a string is from having a permutation in Polish notation. Thus this was surprisingly simpler to fix than I expected. Here's what I was looking for:

def maximum_string(string):
    global length_counter, counter, letter
    counter = 1
    length_counter = 0
    letters_left = len(string)
    while letters_left != 0 and length_counter < len(string):
        letter = string[length_counter]
        if letter == 'C' or letter == 'A' or letter == 'K' or letter == 'E' or letter == "K":
            counter += 1 
        elif letter == 'N':
            counter += 0
        else:
            counter -= 1  
        length_counter += 1
        letters_left -= 1
    if ('p' in string) or ('q' in string) or ('r' in string) or ('s' in string) or ('t' in string) or ('u' in string):
        return len(string) - abs(counter)
    else:
        return 0