Task · strings hard JavaScript ·

Count distinct substrings

/**
 * @param {string} s
 * @returns {number}
 */
function count_distinct_substrings(s)

count_distinct_substrings("abab")  // -> 7
count_distinct_substrings("aaa")  // -> 3
count_distinct_substrings("")  // -> 0

• #1MiniMax M3.1 Flashsolved · 14 of 14 testsanswer in 5.8 s · runtime 388 ms · $0.0009

  ✓	count_distinct_substrings("abab")expected 7	2 ms
  ✓	count_distinct_substrings("aaa")expected 3	<1 ms
  ✓	count_distinct_substrings("")expected 0	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 28 ms✓ 1 ms✓ <1 ms⏱ 292 ms⏱ 22 ms⏱ 35 ms
  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    const maxStates = 2 * n + 1;
    const tr = new Int32Array(maxStates * 26);
    const len = new Int32Array(maxStates);
    const link = new Int32Array(maxStates);
  
    link[0] = -1;
    let size = 1;
    let last = 0;
  
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      const cur = size++;
      len[cur] = len[last] + 1;
  
      let p = last;
      while (p !== -1) {
        const idx = p * 26 + c;
        if (tr[idx] !== 0) break;
        tr[idx] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = tr[p * 26 + c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = size++;
          len[clone] = len[p] + 1;
          link[clone] = link[q];
          const cb = clone * 26, qb = q * 26;
          for (let k = 0; k < 26; k++) tr[cb + k] = tr[qb + k];
          while (p !== -1) {
            const idx = p * 26 + c;
            if (tr[idx] !== q) break;
            tr[idx] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
  
    let total = 0;
    for (let v = 1; v < size; v++) total += len[v] - len[link[v]];
    return total;
  }

• #2Google Gemini 3.8 Flashsolved · 14 of 14 testsanswer in 6.4 s · runtime 487 ms · $0.0026

  ✓	count_distinct_substrings("abab")expected 7	6 ms
  ✓	count_distinct_substrings("aaa")expected 3	1 ms
  ✓	count_distinct_substrings("")expected 0	1 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ 17 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ 330 ms⏱ 99 ms⏱ 25 ms
  Code

  /**
   * @param {string} s
   * @returns {number}
   */
  function count_distinct_substrings(s) {
      const n = s.length;
      if (n === 0) return 0;
      if (n === 1) return 1;
  
      // Suffix Automaton (SAM) approach
      // Max states: 2 * n
      const maxStates = 2 * n;
      const link = new Int32Array(maxStates);
      const len = new Int32Array(maxStates);
      // 26 transitions per state
      const nextState = new Int32Array(maxStates * 26);
      nextState.fill(-1);
  
      link[0] = -1;
      len[0] = 0;
      let sz = 1;
      let last = 0;
  
      for (let i = 0; i < n; i++) {
          const c = s.charCodeAt(i) - 97;
          const cur = sz++;
          len[cur] = len[last] + 1;
  
          let p = last;
          while (p !== -1 && nextState[p * 26 + c] === -1) {
              nextState[p * 26 + c] = cur;
              p = link[p];
          }
  
          if (p === -1) {
              link[cur] = 0;
          } else {
              const q = nextState[p * 26 + c];
              if (len[p] + 1 === len[q]) {
                  link[cur] = q;
              } else {
                  const clone = sz++;
                  len[clone] = len[p] + 1;
                  link[clone] = link[q];
                  // copy transitions
                  const qOffset = q * 26;
                  const cloneOffset = clone * 26;
                  for (let k = 0; k < 26; k++) {
                      nextState[cloneOffset + k] = nextState[qOffset + k];
                  }
  
                  while (p !== -1 && nextState[p * 26 + c] === q) {
                      nextState[p * 26 + c] = clone;
                      p = link[p];
                  }
                  link[q] = clone;
                  link[cur] = clone;
              }
          }
          last = cur;
      }
  
      let ans = 0;
      for (let i = 1; i < sz; i++) {
          ans += len[i] - len[link[i]];
      }
  
      return ans;
  }

• #3Qwen3.8 Max (0902)solved · 14 of 14 testsanswer in 33 s · runtime 952 ms · $0.01

  ✓	count_distinct_substrings("abab")expected 7	2 ms
  ✓	count_distinct_substrings("aaa")expected 3	1 ms
  ✓	count_distinct_substrings("")expected 0	1 ms

  ✓ <1 ms✓ 1 ms✓ 27 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms⏱ 435 ms⏱ 361 ms⏱ 117 ms
  Code

  function count_distinct_substrings(s) {
      const n = s.length;
      if (n === 0) return 0;
      
      // Build suffix array using prefix doubling
      let sa = new Array(n);
      let rank = new Array(n);
      let tmp = new Array(n);
      
      for (let i = 0; i < n; i++) {
          sa[i] = i;
          rank[i] = s.charCodeAt(i);
      }
      
      for (let k = 1; k < n; k <<= 1) {
          const r = rank; // capture current rank
          const cmp = (a, b) => {
              if (r[a] !== r[b]) return r[a] - r[b];
              const ra = a + k < n ? r[a + k] : -1;
              const rb = b + k < n ? r[b + k] : -1;
              return ra - rb;
          };
          sa.sort(cmp);
          
          tmp[sa[0]] = 0;
          for (let i = 1; i < n; i++) {
              tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) < 0 ? 1 : 0);
          }
          [rank, tmp] = [tmp, rank];
          
          if (rank[sa[n-1]] === n - 1) break;
      }
      
      // Kasai's algorithm for LCP array
      // rank[i] = position of suffix i in suffix array
      let lcpSum = 0;
      let h = 0;
      
      for (let i = 0; i < n; i++) {
          if (rank[i] > 0) {
              let j = sa[rank[i] - 1];
              while (i + h < n && j + h < n && s.charCodeAt(i + h) === s.charCodeAt(j + h)) h++;
              lcpSum += h;
              if (h > 0) h--;
          } else {
              h = 0;
          }
      }
      
      return n * (n + 1) / 2 - lcpSum;
  }

• #4SpaceXAI Grok Build 0.1not solved · 11 of 14 testsanswer in 37 s · runtime 1.9 s · $0.02

  ✓	count_distinct_substrings("abab")expected 7	2 ms
  ✓	count_distinct_substrings("aaa")expected 3	1 ms
  ✓	count_distinct_substrings("")expected 0	22 ms

  ✓ 2 ms✓ 1 ms✓ 3 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ time limit exceeded⏱ time limit exceeded⏱ time limit exceeded
  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    const MAX = 2 * n + 10;
    const len = new Array(MAX);
    const link = new Array(MAX);
    const trans = new Array(MAX);
    for (let i = 0; i < MAX; i++) {
      trans[i] = new Array(26).fill(-1);
    }
    let tot = 1;
    len[0] = 0;
    link[0] = -1;
    let last = 0;
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      let cur = tot++;
      len[cur] = len[last] + 1;
      let p = last;
      while (p !== -1 && trans[p][c] === -1) {
        trans[p][c] = cur;
        p = link[p];
      }
      if (p === -1) {
        link[cur] = 0;
      } else {
        let q = trans[p][c];
        if (len[q] === len[p] + 1) {
          link[cur] = q;
        } else {
          let clone = tot++;
          len[clone] = len[p] + 1;
          link[clone] = link[q];
          for (let j = 0; j < 26; j++) {
            trans[clone][j] = trans[q][j];
          }
          while (p !== -1 && trans[p][c] === q) {
            trans[p][c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
    let count = 0;
    for (let i = 1; i < tot; i++) {
      count += len[i] - len[link[i]];
    }
    return count;
  }

  Second try

  solved · 14 of 14 testsanswer in 27 s · $0.01

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	count_distinct_substrings("abab")expected 7	2 ms
  ✓	count_distinct_substrings("aaa")expected 3	<1 ms
  ✓	count_distinct_substrings("")expected 0	<1 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 250 ms⏱ 46 ms⏱ 117 ms

  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    const MAX = 2 * n + 5;
    const len = new Int32Array(MAX);
    const link = new Int32Array(MAX);
    const trans = new Int32Array(MAX * 26);
    trans.fill(-1);
    let tot = 1;
    len[0] = 0;
    link[0] = -1;
    let last = 0;
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      let cur = tot++;
      len[cur] = len[last] + 1;
      let p = last;
      while (p !== -1 && trans[p * 26 + c] === -1) {
        trans[p * 26 + c] = cur;
        p = link[p];
      }
      if (p === -1) {
        link[cur] = 0;
      } else {
        let q = trans[p * 26 + c];
        if (len[q] === len[p] + 1) {
          link[cur] = q;
        } else {
          let clone = tot++;
          len[clone] = len[p] + 1;
          link[clone] = link[q];
          const qbase = q * 26;
          const clonebase = clone * 26;
          for (let j = 0; j < 26; j++) {
            trans[clonebase + j] = trans[qbase + j];
          }
          while (p !== -1 && trans[p * 26 + c] === q) {
            trans[p * 26 + c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
    let count = 0;
    for (let i = 1; i < tot; i++) {
      count += len[i] - len[link[i]];
    }
    return count;
  }

Tokens cost: $0.05 · How rounds are run and scored →