The greedy version below seems to work. This way, we could have constant space aside from one output string. Can someone help find a counter example? I wrote this idea before implementing the straightforward dynamic program (see this revision). Try to maintain sequences of two of the same character as much as possible.
The last section of the code below includes random testing with this and MTO's code.
Python code:
def is_valid(s):
if not s:
return True
char = "x"
count = 0
for c in s:
if c != char:
char, count = c, 1
else:
count += 1
if count == 3:
return False
return True
# My greedy solution
def f(s):
if len(s) == 2:
return s.replace('?', 'a')
aa = ['a', 'a']
bb = ['b', 'b']
out = []
i = 0
a, b = 0, 0
while i < len(s):
if s[i] == 'a' or (s[i] == '?' and b == 2):
if s[i] == 'a' and a == 2:
if s[i-3:i-1] == "??":
out[i-3], out[i-2] = out[i-2], out[i-3]
a -= 1
else:
return ""
out.append('a')
a, b = a + 1, 0
i += 1
elif s[i] == 'b' or (s[i] == '?' and a == 2):
if s[i] == 'b' and b == 2:
if s[i-3:i-1] == "??":
out[i-3], out[i-2] = out[i-2], out[i-3]
b -= 1
else:
return ""
out.append('b')
a, b = 0, b + 1
i += 1
elif i == len(s) - 1:
out.append('a' if b else 'b')
i += 1
elif i == len(s) - 2:
if s[i+1] == '?':
out.extend(aa if b else bb)
else:
out.append('a' if b else 'b')
out.append(s[i+1])
i += 2
elif s[i+1] == '?':
if a:
out.append('a')
a, b = a + 1, 0
else:
out.append('b')
a, b = 0, b + 1
i += 1
elif s[i+1] == 'a':
if a or b < 2:
out.append('b')
a, b = 0, b + 1
else:
out.append('a')
a, b = a + 1, 0
i += 1
elif s[i+1] == 'b':
if b or a < 2:
out.append('a')
a, b = a + 1, 0
else:
out.append('b')
a, b = 0, b + 1
i += 1
return ''.join(out)
# https://stackoverflow.com/a/69322213/2034787
# Code by MTO
def solve(_str):
opposite = {"a": "b", "b": "a"}
curr_idx = 0
output = []
lookahead = lambda x: None if ((curr_idx + x < 0) or (curr_idx + x >= len(_str))) else _str[curr_idx + x]
lookbehind = lambda x: None if curr_idx-x< 0 else output[curr_idx - x]
matches = lambda x, y: x == y or x == None or y == None
is_replacement = lambda x: x == '?'
while curr_idx < len(_str):
curr = lookbehind(1) or 'b'
i = 0
next = lookahead(i)
while is_replacement(next):
i += 1
next = lookahead(i)
if next == None:
# Found the end of the string.
# Append characters opposite to the previous for each ?
for _ in range(i, 0, -1):
curr = opposite[curr]
output.append( curr )
break
if (i > 1):
# Found multiple successive ?s
# Handle the first half of the ?s by
# Append alternating characters from the previous character.
j = 0
while j < i / 2:
curr = opposite[curr]
output.append( curr )
j += 1
# Then handle the second half of the ?s
# append alternating characters to the next character after the ?s.
while j < i:
output.append( next if (j%2) == (i%2) else opposite[next] )
j += 1
elif i == 1:
# Found a single ?
prev = lookbehind(2)
if curr == prev and curr == opposite[next] and next == lookahead(2):
# No solution.
return None
if curr == prev or matches(curr, next):
output.append( opposite[curr] )
else:
output.append( curr )
if next != None:
# Output the next non-? character.
output.append( next )
curr_idx += i + 1
return ''.join(output)
strs = [
"a?bb", # "aabb"
"??abb", # "ababb" or "bbabb" or "baabb"
"a?b?aa", # "aabbaa"
"?bb?",
"aa?bb", # NO SOLUTION
"aa??aa", # "aabbaa"
"ab???bb?",
"????",
"??",
"?????",
"??????",
"?",
"a?",
"a??",
"a???",
"b?",
"b??",
"b???",
"a?a",
"a?b",
"b?a",
"b?b",
"a??a",
"a??b",
"b??a",
"b??b",
"aa?",
"ba?",
"a?bb",
"?bb?",
"??abb",
"a?b?aa",
"ab???bb?",
"aa?bb"
]
for s in strs:
_solve = solve(s)
_f = f(s)
print("%s\n%s, %s, %s, %s\n" % (s, is_valid(_f), is_valid(_solve), _solve, _f))
import random
def get_random(n):
char = 'x'
count = 0
out = []
not_c = lambda c: 'a' if c == 'b' else 'b'
for _ in range(n):
c = ['a', 'b'][int(random.random() * 2)]
if c != char:
out.append(c)
char, count = c, 1
elif count == 2:
out.append(not_c(c))
char, count = not_c(c), 1
else:
out.append(c)
count += 1
for i in range(n):
if int(random.random() * 2):
out[i] = '?'
return ''.join(out)
num_tests = 1000
n = 20
print("Starting random tests...")
for _ in range(num_tests):
s = get_random(n)
_solve = solve(s)
_f = f(s)
valid_solve = is_valid(_solve)
valid_f = is_valid(_f)
if not valid_f or not valid_solve:
print(s, valid_f, valid_solve, _f, _solve)
break
print("Done testing")
