TheStringGame.py

TheStringGame.py

# A Best solution


def GameWithStrings(string):
    n = len(string)
    # has_alice_won = False
    count = 0
    if n >= 3:
        i = 0
        if string[i:i+3] == '))(':
                count += 1
        num_of_close = 0
        num_of_open = 0
        while i < (n - 2):
            if string[i:i+2] == '))':
                num_of_close += 1
                i += 2
            elif string[i] == '(' or string[i] == ')':
                if string[i] == '(':
                    count = num_of_close + 1
                    num_of_open += 1
                if string[i] == ')':
                    count = num_of_open + 1
                # has_alice_won = not has_alice_won
                # string = string[:i] + '())' + string[i+3:]
                # i -= 2
                # if i >= 0:
                #     if string[i:i+2] == '))':
                #         has_alice_won = not has_alice_won
                # if i + 3 < (n - 2):
                #     if string[i+3] == '(':
                #         has_alice_won = not has_alice_won
                # i += 2
            i += 1
    return count % 2 != 0
 
def GameWithStrings(string):
    n = len(string)
    has_alice_won = False
    if n >= 3:
        i = 0
        while i < (n - 2):
            if string[i:i+3] == '))(':
                has_alice_won = not has_alice_won
                # string = string[:i] + '())' + string[i+3:]
                i -= 2
                if i >= 0:
                    if string[i:i+2] == '))':
                        has_alice_won = not has_alice_won
                if i + 3 < (n - 2):
                    if string[i+3] == '(':
                        has_alice_won = not has_alice_won
                i += 2
            i += 1
    return has_alice_won

t = int(input())

while t:
    n = int(input())
    test_string = input()
    if GameWithStrings(test_string):
        print('Alice')
    else:
        print('Bob')
    t -= 1

# A better & efficient code without replace

def GameWithStrings(string):
    n = len(string)
    has_alice_won = False
    if n >= 3:
        i = 0
        while i < (n - 2):
            if string[i:i+3] == '))(':
                has_alice_won = not has_alice_won
                # string = string[:i] + '())' + string[i+3:]
                i -= 2
                if i >= 0:
                    if string[i:i+2] == '))':
                        has_alice_won = not has_alice_won
                i += 3
                if i < (n - 2):
                    if string[i] == '(':
                        has_alice_won = not has_alice_won
            
            i += 1
    return has_alice_won

t = int(input())

while t:
    n = int(input())
    test_string = input()
    if GameWithStrings(test_string):
        print('Alice')
    else:
        print('Bob')
    t -= 1

    
# Wrong Solution  XX
def GameWithStrings(string):
    n = len(string)
    has_alice_won = False
    if n >= 3:
        i = 0
        while i < (n - 2):
            if string[i:i+3] == '))(':
                has_alice_won = not has_alice_won
                string = string[:i] + '())' + string[i+3:]
            i += 1
    return has_alice_won

t = int(input())

while t:
    n = int(input())
    test_string = input()
    has_alice_won = GameWithStrings(test_string)
    if has_alice_won:
        print('Alice')
    else:
        print('Bob')
    t -= 1