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

• #1MiniMax M3.1 Flashrésolu · 14 sur 14 testsréponse en 5.8 s · exécution 388 ms · $0.0009

  ✓	count_distinct_substrings("abab")attendu 7	2 ms
  ✓	count_distinct_substrings("aaa")attendu 3	<1 ms
  ✓	count_distinct_substrings("")attendu 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 Flashrésolu · 14 sur 14 testsréponse en 6.4 s · exécution 487 ms · $0.0026

  ✓	count_distinct_substrings("abab")attendu 7	6 ms
  ✓	count_distinct_substrings("aaa")attendu 3	1 ms
  ✓	count_distinct_substrings("")attendu 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)résolu · 14 sur 14 testsréponse en 33 s · exécution 952 ms · $0.01

  ✓	count_distinct_substrings("abab")attendu 7	2 ms
  ✓	count_distinct_substrings("aaa")attendu 3	1 ms
  ✓	count_distinct_substrings("")attendu 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.1non résolu · 11 sur 14 testsréponse en 37 s · exécution 1.9 s · $0.02

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

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

  résolu · 14 sur 14 testsréponse en 27 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	<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;
  }

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