class Solution {
    fun numMatchingSubseq(s: String, words: Array<String>): Int {
        val map = mutableMapOf<Char, MutableList<Int>>()
        
        for(i in s.indices) {
            if(map[s[i]] == null) {
                map[s[i]] = mutableListOf<Int>(i)
            } else {
                map[s[i]]!!.add(i)
            }
        }
        
        var ans = 0
        
        for(w in words) {
            if(w.length > s.length) {
                continue
            }
            
            var index = 0
            var currentPos = -1
            val checkMap = mutableMapOf<Char, MutableList<Int>>()
            
            for(m in map) {
                checkMap[m.key] = m.value.toMutableList()
            }
            
            while(index < w.length) {
                if(checkMap[w[index]] == null) {
                    break
                }
                
                val indices = checkMap[w[index]]!!
                var left = 0
                var right = indices.size
                
                while(left < right) {
                    val mid = left + (right - left) / 2
                    
                    if(indices[mid] < currentPos) {
                        left = mid + 1
                    } else {
                        right = mid
                    }
                }
                
                if (right >= indices.size) {
                    break
                } else {
                    currentPos = indices[right]
                    indices.removeAt(right)
                    ++index
                }
            }
            
            if(index == w.length) {
                ++ans
            }
        }
        
        return ans
    }
}