"""Original bounded Misra-Gries candidate sketch, exact replay kept separate."""
from collections import Counter
from itertools import product
import json
def candidates(stream,k=3,trace=False):
 if type(k) is not int or not 2<=k<=8:raise ValueError('integer k2..8')
 counts={};steps=[];n=0
 for x in stream:
  if type(x) is not str or len(x)!=1 or n>=64:raise ValueError('at most64 single-codepoint items')
  n+=1;before=dict(counts)
  if x in counts:counts[x]+=1;action='increment'
  elif len(counts)<k-1:counts[x]=1;action='new candidate'
  else:
   action='cancel k distinct occurrences'
   for key in list(counts):
    counts[key]-=1
    if counts[key]==0:del counts[key]
  assert len(counts)<=k-1 and all(v>0 for v in counts.values())
  if trace:steps.append({'index':n-1,'item':x,'before':before,'action':action,'after':dict(counts)})
 return counts,n,steps
def verified(data,k):
 c,n,tr=candidates(iter(data),k,True);exact=Counter(data)
 return c,n,tr,sorted(x for x in c if exact[x]*k>n),dict(exact)
def demo():
 rows=[]
 for data in ['ABCABCD','AAABBCDAA','AABBCC','']:
  c,n,tr,h,ex=verified(data,3);oracle=sorted(x for x,v in ex.items() if v*3>n);assert h==oracle
  rows.append({'data':data,'n':n,'residual_counters':c,'actual_full_counts':ex,'verified_strict_heavy':h,'trace':tr})
 assert rows[0]['residual_counters']=={'D':1} and rows[0]['verified_strict_heavy']==[]
 checks=0
 for n in range(8):
  for p in product('ABC',repeat=n):
   s=''.join(p);ex=Counter(s)
   for k in [2,3,4]:
    c,seen,_=candidates(iter(s),k);heavy={x for x,v in ex.items() if v*k>seen};assert heavy<=set(c)
    assert {x for x in c if ex[x]*k>seen}==heavy;checks+=1
 rejected=[]
 for k in [True,1,9,2.5]:
  try:candidates(iter('A'),k)
  except ValueError:rejected.append(repr(k))
  else:raise AssertionError('expected rejection')
 return {'k3_examples':rows,'finite_sequence_k_checks':checks,'oracle':'separate full Counter; not sketch memory','strict_threshold':'frequency*k > n','max_sketch_counters':'k-1','replay_required_for_exact_verification':True,'invalid_k_rejected':rejected,'real_customer_stream':False}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))