Défi · chaînes difficile 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 Flashrésolu · 14 sur 14 testsréponse en 5.2 s · exécution 500 ms · $0.0026

  ✓	count_distinct_substrings("abab")attendu 7	3 ms
  ✓	count_distinct_substrings("aaa")attendu 3	1 ms
  ✓	count_distinct_substrings("")attendu 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 Lunanon résolu · 13 sur 14 testsréponse en 6.9 s · exécution 1.2 s · $0.0004

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

  ✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms⏱ 481 ms⏱ délai limite dépassé⏱ 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 essai

  non résolu · 11 sur 14 testsréponse en 5.6 s · $0.0005

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

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

  ✓ 1 ms✓ 3 ms✓ 2 ms✓ 1 ms✓ 1 ms✗ mauvaise réponse✓ 1 ms✗ mauvaise réponse⏱ 545 ms⏱ délai limite dépassé⏱ 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.1non résolu · 13 sur 14 testsréponse en 29 s · exécution 1.8 s · $0.01

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

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 4 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ délai limite dépassé⏱ 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 essai

  non résolu · 12 sur 14 testsréponse en 28 s · $0.01

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

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

  ✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ mauvaise réponse⏱ 37 ms⏱ mauvaise réponse

  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 Flashnon résolu · 12 sur 14 testsréponse en 6.9 s · exécution 1.8 s · $0.0007

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

  ✓ 2 ms✓ <1 ms✓ 4 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ délai limite dépassé⏱ 329 ms⏱ délai limite dépassé
  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 essai

  non résolu · 1 sur 14 testsréponse en 2.6 s · $0.0005

  Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.

  ✗	count_distinct_substrings("abab")attendu 7obtenu 0	4 ms
  ✗	count_distinct_substrings("aaa")attendu 3obtenu 0	2 ms
  ✓	count_distinct_substrings("")attendu 0	1 ms

  ✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse✗ mauvaise réponse⏱ mauvaise réponse⏱ mauvaise réponse⏱ mauvaise réponse

  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;
  }

Coût en jetons: $0.03 · Déroulement et calcul des scores →