Pseudo Min Max

843. Guess the Word

https://leetcode.com/problems/guess-the-word/

I am calling this strategy as pseudo minmax strategy as it is not the same as it is commonly recognized in AI area.

Naive way will get wrong answer as we may need more than 10 times to guess.

TLE

class Solution:
    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
        def match(w0, w):
            return sum(w0[i]==w[i] for i in range(6))
        words = wordlist[:]
        while True:
            n = master.guess(words[0])
            if n==6:break
            words = [w for w in words[1:] if match(words[0], w)==n]

Inspired by this post:
https://leetcode.com/problems/guess-the-word/discuss/134251/Optimal-MinMax-Solution-(+-extra-challenging-test-cases)
If we caculate the distance of this_word to all the rest words, we will get a histogram such as:
case A:
0 : 10
1: 10
2: 10
3: 10
4: 10
5: 10
6: 10
or
case B
0: 0
1:0
2:0
3:0
4:0
5:10
6:60

Case B, in the worst case, we will have to explore 60 candidates. For case A, in the worst case, we only need explore 10 candidates. So we prefer to choose a pattern close to case A. It can be picked up by find a word which has a minimum maximum histogram value. Recall, Case A, maximum histogram value is 10. Case B is 60.
This is the critical part of how to solve this problem.

time (80 ms)

class Solution:
    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
        def match(w1, w2):
            return sum(c1==c2 for c1, c2 in zip(w1, w2))
        cnt = collections.defaultdict(lambda :[0]*7)
        for w1, w2 in itertools.combinations(wordlist, 2):
            exact_match = match(w1,w2)
            cnt[w1][exact_match]+=1
            cnt[w2][exact_match]+=1
            
        while True:
            guess = min(wordlist, key=lambda word:max(cnt[word]))
            n = master.guess(guess)
            if n==6:break
            wordlist = [w for w in wordlist if match(w, guess) == n]

cnt is used to do the histogram. For example, if we have a word ‘aaaaaa’, then we will have a dictionary of cnt as
cnt[“aaaaaa”] = {0: x0,
1: x1,
…
6:x6}
x0 , x1 … x6 are the counter of the distance between this word to all rest words.
Then each time, we pick up a word that has a minimum value of max(x0, x1, x2, …x6). By using this strategy, we can avoid the worst-case to make sure we can successfully do it in about 10 times guessing.

Time (100 ms)

class Solution:
   
    def findSecretWord(self, wordlist: List[str], master: 'Master') -> None:
        def match(w1, w2):
            return sum(c1==c2 for c1, c2 in zip(w1, w2))
        cnt = collections.defaultdict(lambda : collections.defaultdict(int))
        for w1, w2 in itertools.combinations(wordlist, 2):
            res = match(w1,w2)
            cnt[w1][res]+=1
            cnt[w2][res]+=1
            
        while True:
            guess = min(wordlist, key=lambda word:max(cnt[word].values()))
            n = master.guess(guess)
            if n==6:break
            wordlist = [w for w in wordlist if match(w, guess) == n]

828. Unique Letter String

https://leetcode.com/problems/unique-letter-string/discuss/128952/One-pass-O(N)-Straight-Forward

class Solution:
    def uniqueLetterString(self, S: str) -> int:
        index = {c: [-1, -1] for c in string.ascii_uppercase}
        res = 0
        for i, c in enumerate(S):
            k, j = index[c]
            res += (i - j) * (j - k)
            index[c] = [j, i]
        for c in index:
            k, j = index[c]
            res += (len(S) - j) * (j - k)
        return res % (10**9 + 7)