Java binary search using TreeSet got TLE

  • 3

    Java binary search using TreeSet, but got TLE. For single s, it performs worse than linear 2-pointer solution for sure, but if there are many s like in the follow up, should it be better since t only got processed once?

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            int sLen = s.length(), tLen = t.length();
            if(sLen == 0) return true;
            if(sLen > tLen) return false;
            Map<Character, TreeSet<Integer>> map = new HashMap<>();
            for(int i = 0; i < tLen; i++) {
                char c = t.charAt(i);
                if(!map.containsKey(c)) map.put(c, new TreeSet<Integer>());
            int lowerIndex = -1;
            for(int j = 0; j < sLen; j++) {
                char c = s.charAt(j);
                if(!map.containsKey(c)) return false;
                Integer index = map.get(c).higher(lowerIndex);
                if(index == null) return false;
                lowerIndex = index;
            return true;

  • 0

    I made optimizations of your code to avoid extra lookups and got MTE. Interesting that TreeSet adds this overhead, it works with ArrayList and custom "upper bound"

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.