1593.js

/** ------------------------------------------------------------------------------
 * 
 * 1593. Split a String Into the Max Number of Unique Substrings
 * Topics: Backtracking, Hash Table
 * https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings/description/?envType=daily-question&envId=2024-10-21
 * 
 ------------------------------------------------------------------------------ */

/**
 * @param {string} s
 * @return {number}
 */
var maxUniqueSplit = function (s) {
  const set = new Set()
  let result = 1
  function bfs(startIndex) {
    if (startIndex === s.length) {
      result = Math.max(result, set.size)
      return
    }

    if (set.size + (s.length - startIndex) <= result) {
      return
    }

    for (let endIndex = startIndex + 1; endIndex <= s.length; endIndex++) {
      let str = s.slice(startIndex, endIndex)
      if (!set.has(str)) {
        set.add(str)
        bfs(endIndex)
        set.delete(str)
      }
    }
  }

  bfs(0)

  return result
}

var maxUniqueSplit = function (s) {
  const set = new Set()

  const traverse = (s, start, set) => {
    if (start === s.length) {
      return 0
    }

    let max = 0

    for (let i = start + 1; i <= s.length; i++) {
      let substr = s.substring(start, i)
      if (set.has(substr)) {
        continue
      }

      set.add(substr)
      max = Math.max(max, 1 + traverse(s, i, set))
      set.delete(substr)
    }

    return max
  }

  return traverse(s, 0, set)
}

console.log(maxUniqueSplit("ababccc"))