给定字符串 s,每轮给出一个对字符集的排列,表示优先级(越靠前优先级越高)。在该轮中,每个位置 i>0 的字符 s[i] 若其左邻居 s[i-1] 的优先级更高,则 s[i] 被同时消灭。也就是说:设 rank[c] 为该轮中字符 c 的名次(0 表示最高),那么当且仅当 rank[s[i-1]] < rank[s[i]] 时,位置 i 会被删除;其它位置保留。所有删除在本轮“同时”发生,判断时都以本轮开始时的原串为准。
据此可用线性扫描模拟每一轮:
rank[26]。s[0],对 i=1..len-1,若 rank[s[i-1]] >= rank[s[i]] 则保留 s[i],否则丢弃。小饹有一个长度为 n 的字符串 s ,该字符串由 m 种小写英文字母组成,该字符串会经过 q 轮迭代,每一轮迭代前会先给出字符集的排列,字符在排列中出现的位置越靠前,则表明该字符在该轮迭代中优先级更高。每一轮选代中,优先级更高的字符会同时“消灭“右侧优先级更低的相邻字符。
你需要回答经过 q 轮迭代后,字符串是否只剩下一种字符,如果是,输出一行“YES”,然后输出最早第几轮迭代后字符串只剩下一种字符、迭代结束后字符串的长度;否则,输出一行“NO”,然后输出一行迭代结束后的字符串。