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

• #1Google Gemini 3.8 Flashsolved · 14 of 14 testsanswer in 5.2 s · runtime 500 ms · $0.0026

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

  ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 304 ms⏱ 106 ms⏱ 78 ms
  Code

  /**
   * @param {string} s
   * @returns {number}
   */
  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    // Build Suffix Automaton (SAM)
    // Each state has: len, link, next
    // Number of states is at most 2 * n
    const maxStates = 2 * n;
    const len = new Int32Array(maxStates);
    const link = new Int32Array(maxStates);
    // Using an array of maps or flattened array for transitions
    // Since alphabet is small (a-z, size 26), we can use Int32Array(maxStates * 26)
    const next = new Int32Array(maxStates * 26);
    next.fill(-1);
  
    len[0] = 0;
    link[0] = -1;
    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 && next[p * 26 + c] === -1) {
        next[p * 26 + c] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = next[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];
          for (let j = 0; j < 26; j++) {
            next[clone * 26 + j] = next[q * 26 + j];
          }
          while (p !== -1 && next[p * 26 + c] === q) {
            next[p * 26 + c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
  
    let total = 0;
    for (let i = 1; i < sz; i++) {
      total += len[i] - len[link[i]];
    }
  
    return total;
  }

• #2OpenAI GPT-6 Lunanot solved · 13 of 14 testsanswer in 6.9 s · runtime 1.2 s · $0.0004

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

  ✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms⏱ 481 ms⏱ time limit exceeded⏱ 307 ms
  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    // Suffix array by doubling, using counting sort on integer ranks.
    let sa = new Int32Array(n);
    let rank = new Int32Array(n);
    let nextRank = new Int32Array(n);
    let tmp = new Int32Array(n);
  
    for (let i = 0; i < n; i++) {
      sa[i] = i;
      rank[i] = s.charCodeAt(i) - 97;
    }
  
    for (let k = 1; k < n; k <<= 1) {
      // Stable counting sort by second key, then first key.
      const maxRank = Math.max(26, n);
      const counts = new Int32Array(maxRank + 2);
  
      for (let i = 0; i < n; i++) {
        const key = sa[i] + k < n ? rank[sa[i] + k] + 1 : 0;
        counts[key]++;
      }
      let sum = 0;
      for (let i = 0; i < counts.length; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const pos = sa[i];
        const key = pos + k < n ? rank[pos + k] + 1 : 0;
        tmp[counts[key]++] = pos;
      }
  
      counts.fill(0);
      for (let i = 0; i < n; i++) counts[rank[tmp[i]] + 1]++;
      sum = 0;
      for (let i = 0; i < counts.length; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const pos = tmp[i];
        sa[counts[rank[pos] + 1]++] = pos;
      }
  
      let classes = 1;
      nextRank[sa[0]] = 0;
      for (let i = 1; i < n; i++) {
        const a = sa[i - 1], b = sa[i];
        const a2 = a + k < n ? rank[a + k] : -1;
        const b2 = b + k < n ? rank[b + k] : -1;
        if (rank[a] !== rank[b] || a2 !== b2) classes++;
        nextRank[b] = classes - 1;
      }
      [rank, nextRank] = [nextRank, rank];
      if (classes === n) break;
    }
  
    // Kasai LCP; each suffix contributes its length minus its LCP with
    // the preceding suffix in sorted order.
    const inverse = new Int32Array(n);
    for (let i = 0; i < n; i++) inverse[sa[i]] = i;
  
    let lcp = 0;
    let result = 0;
    for (let i = 0; i < n; i++) {
      const order = inverse[i];
      if (order === 0) continue;
      const j = sa[order - 1];
      while (i + lcp < n && j + lcp < n && s.charCodeAt(i + lcp) === s.charCodeAt(j + lcp)) {
        lcp++;
      }
      result += n - i - lcp;
      if (lcp > 0) lcp--;
    }
    // The first suffix has no preceding suffix.
    result += n - sa[0];
    return result;
  }

  Second try

  not solved · 11 of 14 testsanswer in 5.6 s · $0.0005

  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	6 ms
  ✓	count_distinct_substrings("aaa")expected 3	2 ms
  ✓	count_distinct_substrings("")expected 0	1 ms

  ✓ 1 ms✓ 3 ms✓ 2 ms✓ 1 ms✓ 1 ms✗ wrong answer✓ 1 ms✗ wrong answer⏱ 545 ms⏱ time limit exceeded⏱ 266 ms

  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    // Suffix array via radix-sorted prefix doubling.
    let sa = new Int32Array(n);
    let rank = new Int32Array(n);
    let nextRank = new Int32Array(n);
    let order = new Int32Array(n);
    let temp = new Int32Array(n);
  
    for (let i = 0; i < n; i++) {
      sa[i] = i;
      rank[i] = s.charCodeAt(i) - 97;
    }
  
    const counts = new Int32Array(n + 1);
  
    for (let k = 1; k < n; k *= 2) {
      // Sort suffix indices by second rank, then first rank.
      counts.fill(0);
      for (let i = 0; i < n; i++) {
        const p = sa[i];
        counts[p + k < n ? rank[p + k] + 1 : 0]++;
      }
      let sum = 0;
      for (let i = 0; i <= n; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const p = sa[i];
        const key = p + k < n ? rank[p + k] + 1 : 0;
        temp[counts[key]++] = p;
      }
  
      counts.fill(0);
      for (let i = 0; i < n; i++) counts[rank[temp[i]] + 1]++;
      sum = 0;
      for (let i = 0; i <= n; i++) {
        const c = counts[i];
        counts[i] = sum;
        sum += c;
      }
      for (let i = 0; i < n; i++) {
        const p = temp[i];
        order[counts[rank[p] + 1]++] = p;
      }
  
      let classes = 1;
      nextRank[order[0]] = 0;
      for (let i = 1; i < n; i++) {
        const a = order[i - 1], b = order[i];
        const a2 = a + k < n ? rank[a + k] : -1;
        const b2 = b + k < n ? rank[b + k] : -1;
        if (rank[a] !== rank[b] || a2 !== b2) classes++;
        nextRank[b] = classes - 1;
      }
      const oldRank = rank;
      rank = nextRank;
      nextRank = oldRank;
      const oldSa = sa;
      sa = order;
      order = oldSa;
      if (classes === n) break;
    }
  
    const inverse = new Int32Array(n);
    for (let i = 0; i < n; i++) inverse[sa[i]] = i;
  
    let answer = 0;
    let h = 0;
    for (let i = 0; i < n; i++) {
      const r = inverse[i];
      if (r === 0) continue;
      const j = sa[r - 1];
      while (i + h < n && j + h < n && s.charCodeAt(i + h) === s.charCodeAt(j + h)) h++;
      answer += n - i - h;
      if (h) h--;
    }
    return answer + n - sa[0];
  }

• #3SpaceXAI Grok Build 0.1not solved · 13 of 14 testsanswer in 29 s · runtime 1.8 s · $0.01

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

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 4 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ time limit exceeded⏱ 379 ms⏱ 511 ms
  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
    const MAX = 2 * n;
    const len = new Array(MAX).fill(0);
    const link = new Array(MAX).fill(0);
    const trans = Array.from({ length: MAX }, () => new Array(26).fill(-1));
    len[0] = 0;
    link[0] = -1;
    let sz = 1;
    let last = 0;
    function addChar(c) {
      const cur = sz++;
      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 {
        const q = trans[p][c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = sz++;
          len[clone] = len[p] + 1;
          trans[clone] = trans[q].slice();
          link[clone] = link[q];
          while (p !== -1 && trans[p][c] === q) {
            trans[p][c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      addChar(c);
    }
    let ans = 0;
    for (let i = 1; i < sz; i++) {
      ans += len[i] - len[link[i]];
    }
    return ans;
  }

  Second try

  not solved · 12 of 14 testsanswer in 28 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	3 ms

  ✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ wrong answer⏱ 37 ms⏱ wrong answer

  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).fill(-1);
    len[0] = 0;
    link[0] = -1;
    let sz = 1;
    let last = 0;
    function addChar(c) {
      const cur = sz++;
      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 {
        const q = trans[p * 26 + c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = sz++;
          len[clone] = len[p] + 1;
          const qidx = q * 26;
          const cloneidx = clone * 26;
          for (let i = 0; i < 26; i++) {
            trans[cloneidx + i] = trans[qidx + i];
          }
          link[clone] = link[q];
          p = last;
          while (p !== -1 && trans[p * 26 + c] === q) {
            trans[p * 26 + c] = clone;
            p = link[p];
          }
          link[q] = clone;
          link[cur] = clone;
        }
      }
      last = cur;
    }
    for (let i = 0; i < n; i++) {
      const c = s.charCodeAt(i) - 97;
      addChar(c);
    }
    let ans = 0;
    for (let i = 1; i < sz; i++) {
      ans += len[i] - len[link[i]];
    }
    return ans;
  }

• #4MiniMax M3.1 Flashnot solved · 12 of 14 testsanswer in 6.9 s · runtime 1.8 s · $0.0007

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

  ✓ 2 ms✓ <1 ms✓ 4 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ time limit exceeded⏱ 329 ms⏱ time limit exceeded
  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    const len = [0];
    const link = [-1];
    const next = [Object.create(null)];
    let last = 0;
  
    for (let i = 0; i < n; i++) {
      const c = s[i];
      const cur = len.length;
      len.push(len[last] + 1);
      link.push(0);
      next.push(Object.create(null));
  
      let p = last;
      while (p !== -1 && next[p][c] === undefined) {
        next[p][c] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = next[p][c];
        if (len[p] + 1 === len[q]) {
          link[cur] = q;
        } else {
          const clone = len.length;
          len.push(len[p] + 1);
          link.push(link[q]);
          next.push(Object.assign(Object.create(null), next[q]));
  
          while (p !== -1 && next[p][c] === q) {
            next[p][c] = clone;
            p = link[p];
          }
  
          link[q] = clone;
          link[cur] = clone;
        }
      }
  
      last = cur;
    }
  
    let result = 0;
    for (let v = 1; v < len.length; v++) {
      result += len[v] - len[link[v]];
    }
    return result;
  }

  Second try

  not solved · 1 of 14 testsanswer in 2.6 s · $0.0005

  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 7returned 0	4 ms
  ✗	count_distinct_substrings("aaa")expected 3returned 0	2 ms
  ✓	count_distinct_substrings("")expected 0	1 ms

  ✗ wrong answer✗ wrong answer✗ wrong answer✗ wrong answer✗ wrong answer✗ wrong answer✗ wrong answer✗ wrong answer⏱ wrong answer⏱ wrong answer⏱ wrong answer

  Code

  function count_distinct_substrings(s) {
    const n = s.length;
    if (n === 0) return 0;
  
    const maxStates = 2 * n;
    const trans = new Int32Array(maxStates * 26);
    const len = new Int32Array(maxStates);
    const link = new Int32Array(maxStates);
  
    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 (trans[idx] !== 0) break;
        trans[idx] = cur;
        p = link[p];
      }
  
      if (p === -1) {
        link[cur] = 0;
      } else {
        const q = trans[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 src = q * 26;
          const dst = clone * 26;
          for (let j = 0; j < 26; j++) trans[dst + j] = trans[src + j];
  
          while (p !== -1) {
            const idx = p * 26 + c;
            if (trans[idx] !== q) break;
            trans[idx] = clone;
            p = link[p];
          }
  
          link[q] = clone;
          link[cur] = clone;
        }
      }
  
      last = cur;
    }
  
    let result = 0;
    for (let v = 1; v < size; v++) {
      result += len[v] - len[link[v]];
    }
    return result;
  }

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