def KDistinctCharacter(s,k):

   ans  = []
   word = dict()
   len  = 0
   i    = 0

   for ch in list(s):
      if( ch in word and i - word[ch] < k ):
         len = i - word[ch]
      else:
         len += 1
      word[ch] = i

      if( len >= k ):
         sub = s[i - k + 1:i + 1]
         if sub not in ans:
            ans.append(sub)
      i += 1

   return ans

######
# 測資

s = 'awaglknagawunagwkwagl'
k = 4
a = KDistinctCharacter(s,k)
print("ans:", a)


※ 引述《suhang (suhang)》之銘言：
: https://imgur.com/a/2GAU3
: my solution
: https://repl.it/@shih_hsuanhsu/KDistinctCharacter
: def KDistinctCharacter3
: def KDistinctCharacter2
: 兩個方法應該都正確，但是複雜度為O(nk)
: 網路上高手說可以做到O(n)
: 我試著又寫了 KDistinctCharacter
: 但是我想不透該怎麼做
: 求助!
: 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.131.210
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1520934332.A.CD8.html
※ 編輯: cutekid (36.233.35.113), 03/14/2018 10:15:44