JS time limit exceeded


  • 0
    Y

    Anyone know why I'm getting TLE, or what the actual runtime is (it seems like its O(n))?

    const startCharCode = 'A'.charCodeAt()
    
    // time limit exceeded, the same implementation in Java passes
    //
    // https://leetcode.com/problems/minimum-window-substring/
    function minWindow(string, query) {
      const sHash = Array(58).fill(0)
      const qHash = Array(58).fill(0)
      for (const qLetter of query) {
        qHash[qLetter.charCodeAt() - startCharCode] += 1
      }
      function sHashContainsQuery() {
        for (const qLetter of query) {
          const charCode = qLetter.charCodeAt()
          if (sHash[charCode - startCharCode] < qHash[charCode - startCharCode]) {
            return false
          }
        }
        return true
      }
      let min = ''
      for (let i = 0, j = 0; j < string.length; j++) {
        sHash[string.charCodeAt(j) - startCharCode] += 1
        if (!sHashContainsQuery()) {
          continue
        }
        while (i <= j) {
          const charCode = string.charCodeAt(i) - startCharCode
          if (sHash[charCode] === qHash[charCode]) {
            break
          }
          sHash[charCode] -= 1
          i += 1
        }
        if (!min || (j - i + 1 < min.length)) {
          min = string.substring(i, j + 1)
        }
      }
      return min
    }
    

Log in to reply
 

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