[Python] Why does this greedy algorithm work? The problem is "Lexicographically Smallest...

I'm trying to figure out why this solution to a LeetCode problem works.

Context

The problem statement: https://leetcode.com/problems/lexicographically-smallest-generated-string/description/. This question was from a recent LeetCode contest.

I looked at the solutions from the top participants in the contest, and most of them used essentially a greedy solution that goes like this:

1. Initialize an 'ans' array where all positions in the array are '?' indicating the character at that position is undecided. All positions are marked as 'unfixed' initially, indicating that the character at this position can be freely changed.
2. Fill up all positions i where req = 'T', because these are forced. Mark these positions as fixed.
   [*]Check for any contradictions / impossible-to-fulfil criteria.
   [*]Fill up all '?' positions with 'a'.
   [*]Greedily adjust the non-fixed 'a' positions to satisfy any req = 'F' criteria. We do so by flipping a non-fixed 'a' to a 'b', and marking that position as fixed. To choose which 'a' to flip, we take the rightmost non-fixed 'a'.
   

My question is why does this algorithm work?

• Steps 1-4 all makes sense.
• However, I cannot prove to myself that doing the greedy step in 5 produces the optimal solution.
  • For example, you might flip an 'a' to 'b' to satisfy a req[5] = 'F'. But this might cause another req[8] = 'F' to be violated. Which may then cause a cascade of flips.
  • There are also other possible problems like why don't we need to check if we can 'unflip' a position that we previously flipped?

Here is a commented solution which I implemented based on the pseudocode. This solution passes all test cases.

'''
1. Initially all positions in the ans are '?'.
2. Fill up all positions i where req = 'T', because these are forced. Mark these positions as fixed.
3. Check for any contradictions / impossible-to-fulfil criteria.
4. Fill up all '?' positions with 'a'.
5. Greedily adjust the non-fixed 'a' positions to satisfy any req = 'F' criteria.
We do so by flipping a non-fixed 'a' to a 'b', and marking that position as fixed.
To choose which 'a' to flip, we take the rightmost non-fixed 'a'.
'''

class Solution:
def generateString(self, req: str, pattern: str) -> str:
n=len(req)
m=len(pattern)
ans = ['?'] * (n+m-1)
fixed = [False] * (n+m-1)
for i in range(n):
if req=='T':
# Fill this location with the pattern
for j in range(m):
if fixed[i+j] and ans[i+j] != pattern[j]:
# There is a contradiction already
return ""
ans[i+j] = pattern[j]
fixed[i+j] = True

# Check for an unsatisfiable 'F' criteria
for i in range(n):
if req=='F' and ''.join(ans[i:i+m]) == pattern:
return ""

# Greedily fill '?' with 'a'
for i in range(len(ans)):
if ans=='?':
ans='a'

# Check for unsatisfied 'F' criteria.
for i in range(n):
if req == 'F':
# We must make sure it does not match
same = (pattern == "".join(ans[i:i+m]))
if not same:
continue
# We have an unstaified 'F' criteria here
# Fix it by flipping the rightmost flippable position to 'b'.
else:
# flip the rightmost char
for j in range(m-1, -1, -1):
if not fixed[i+j]:
ans[i+j] = 'b'
break

return "".join(ans)

Continue reading...