Breaking Strings

Computer Science Level 4

You have an unwanted string of characters. Unfortunately, you can't just apply delete because your keyboard's d key isn't working. The only operation is break , which remove a subsegment consists of the same characters and concatenate both ends. What is the minimum number of break you need to apply to completely delete this string ?

Explicit Example

The answer for string ababa is 3.
The answer for string abbccbba is 3.
The answer for string abcdefghi is 9.

The answer is 12.

1 solution

Maurice van Peursem
Nov 2, 2018

I think the correct answer is not 12, but 13!

Python3

Str = 'ceefgeeacfadgfbcgbcb'

def Reduce(Str, Level):
    GStr = Str[:]
    Continue = True
    LLevel = Level
    while Continue:
        Continue = False
        Ptr = 0                     # remove all sequences, aa..a -> a
        while Ptr < len(GStr):
            Chr = GStr[Ptr]
            Ptr += 1
            while Ptr < len(GStr) and GStr[Ptr] == Chr:
                del GStr[Ptr]
                Continue = True     # repeat if a sequence is removed
        for Chr in set(GStr):       # remove all singles: aba -> aa
            if(GStr.count(Chr) == 1):
                GStr.remove(Chr)
                LLevel += 1         # remove single, one more step
                Continue = True     # repeat if a single is removed
    Ptr = 1
    NLevel = LLevel
    while Ptr < len(GStr) - 1:      # remove second, third ... last but one char
                                    # one by one and reduce resulting string
                                    # find the shortest nb of steps
        LStr = GStr[:]
        del LStr[Ptr]
        Val = Reduce(LStr, NLevel + 1)
        if NLevel == LLevel:
            LLevel = Val
        else:
            LLevel = min(LLevel, Val)
        Ptr += 1
    return LLevel


print(Str, Reduce(list(Str), 0))

Breaking Strings

The answer is 12.

1 solution

0 pending reports