टास्क · स्ट्रिंग्स कठिन 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 Flashहल किया गया · 14 में से 14 टेस्ट्स पासजवाब का समय 5.8 s · रनटाइम 388 ms · $0.0009

  ✓	count_distinct_substrings("abab")अपेक्षित 7	2 ms
  ✓	count_distinct_substrings("aaa")अपेक्षित 3	<1 ms
  ✓	count_distinct_substrings("")अपेक्षित 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
  कोड

  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 Flashहल किया गया · 14 में से 14 टेस्ट्स पासजवाब का समय 6.4 s · रनटाइम 487 ms · $0.0026

  ✓	count_distinct_substrings("abab")अपेक्षित 7	6 ms
  ✓	count_distinct_substrings("aaa")अपेक्षित 3	1 ms
  ✓	count_distinct_substrings("")अपेक्षित 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
  कोड

  /**
   * @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)हल किया गया · 14 में से 14 टेस्ट्स पासजवाब का समय 33 s · रनटाइम 952 ms · $0.01

  ✓	count_distinct_substrings("abab")अपेक्षित 7	2 ms
  ✓	count_distinct_substrings("aaa")अपेक्षित 3	1 ms
  ✓	count_distinct_substrings("")अपेक्षित 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
  कोड

  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.1हल नहीं हुआ · 14 में से 11 टेस्ट्स पासजवाब का समय 37 s · रनटाइम 1.9 s · $0.02

  ✓	count_distinct_substrings("abab")अपेक्षित 7	2 ms
  ✓	count_distinct_substrings("aaa")अपेक्षित 3	1 ms
  ✓	count_distinct_substrings("")अपेक्षित 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)
  कोड

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

  दूसरा प्रयास

  हल किया गया · 14 में से 14 टेस्ट्स पासजवाब का समय 27 s · $0.01

  मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।

  ✓	count_distinct_substrings("abab")अपेक्षित 7	2 ms
  ✓	count_distinct_substrings("aaa")अपेक्षित 3	<1 ms
  ✓	count_distinct_substrings("")अपेक्षित 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

  कोड

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

टोकन लागत: $0.05 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →