टास्क · स्ट्रिंग्स कठिन JavaScript ·

Shortest palindrome by prepending

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

shortest_palindrome("aacecaaa")  // -> "aaacecaaa"
shortest_palindrome("abcd")  // -> "dcbabcd"
shortest_palindrome("")  // -> ""

• #1OpenAI GPT-6 Lunaहल किया गया · 15 में से 15 टेस्ट्स पासजवाब का समय 2.9 s · रनटाइम 409 ms · $0.0001

  ✓	shortest_palindrome("aacecaaa")अपेक्षित "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")अपेक्षित "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")अपेक्षित ""	21 ms

  ✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ 179 ms⏱ 88 ms⏱ 104 ms
  कोड

  function shortest_palindrome(s) {
    const n = s.length;
    if (n < 2) return s;
  
    // Compute the longest palindromic prefix via the KMP prefix function
    // on s followed by a separator and the reverse of s.
    const rev = s.split('').reverse().join('');
    const text = s + '#' + rev;
    const pi = new Uint32Array(text.length);
  
    for (let i = 1; i < text.length; i++) {
      let j = pi[i - 1];
      while (j > 0 && text[i] !== text[j]) j = pi[j - 1];
      if (text[i] === text[j]) j++;
      pi[i] = j;
    }
  
    const palPrefixLength = pi[text.length - 1];
    return rev.slice(0, n - palPrefixLength) + s;
  }

• #2Google Gemini 4 Argonहल किया गया · 15 में से 15 टेस्ट्स पासजवाब का समय 17 s · रनटाइम 518 ms · $0.0036

  ✓	shortest_palindrome("aacecaaa")अपेक्षित "aaacecaaa"	2 ms
  ✓	shortest_palindrome("abcd")अपेक्षित "dcbabcd"	2 ms
  ✓	shortest_palindrome("")अपेक्षित ""	4 ms

  ✓ <1 ms✓ <1 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ <1 ms⏱ 267 ms⏱ 77 ms⏱ 155 ms
  कोड

  /**
   * @param {string} s
   * @returns {string}
   */
  function shortest_palindrome(s) {
      const n = s.length;
      if (n <= 1) return s;
  
      // Reverse s
      let rev = "";
      for (let i = n - 1; i >= 0; i--) {
          rev += s[i];
      }
  
      if (s === rev) return s;
  
      const combined = s + "#" + rev;
      const m = combined.length;
      const pi = new Int32Array(m);
  
      let j = 0;
      for (let i = 1; i < m; i++) {
          while (j > 0 && combined.charCodeAt(i) !== combined.charCodeAt(j)) {
              j = pi[j - 1];
          }
          if (combined.charCodeAt(i) === combined.charCodeAt(j)) {
              j++;
          }
          pi[i] = j;
      }
  
      const longestPalindromicPrefixLen = pi[m - 1];
      return rev.slice(0, n - longestPalindromicPrefixLen) + s;
  }

• #2SpaceXAI Grok 4.7हल किया गया · 15 में से 15 टेस्ट्स पासजवाब का समय 47 s · रनटाइम 590 ms · $0.02

  ✓	shortest_palindrome("aacecaaa")अपेक्षित "aaacecaaa"	3 ms
  ✓	shortest_palindrome("abcd")अपेक्षित "dcbabcd"	3 ms
  ✓	shortest_palindrome("")अपेक्षित ""	<1 ms

  ✓ 2 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms⏱ 265 ms⏱ 168 ms⏱ 139 ms
  कोड

  /**
   * @param {string} s
   * @returns {string}
   */
  function shortest_palindrome(s) {
    const n = s.length;
    if (n <= 1) return s;
    const revArr = new Array(n);
    for (let i = 0; i < n; i++) {
      revArr[i] = s[n - 1 - i];
    }
    const temp = s + '#' + revArr.join('');
    const m = temp.length;
    const lps = new Array(m).fill(0);
    let len = 0;
    for (let i = 1; i < m; i++) {
      while (len > 0 && temp[i] !== temp[len]) {
        len = lps[len - 1];
      }
      if (temp[i] === temp[len]) {
        len++;
      }
      lps[i] = len;
    }
    const palLen = lps[m - 1];
    const suffixLen = n - palLen;
    if (suffixLen === 0) return s;
    const prependArr = new Array(suffixLen);
    for (let i = 0; i < suffixLen; i++) {
      prependArr[i] = s[n - 1 - i];
    }
    return prependArr.join('') + s;
  }

• #4Qwen3 Coder Nextहल नहीं हुआ · 15 में से 6 टेस्ट्स पासजवाब का समय 7.7 s · रनटाइम 403 ms · $0.0005

  ✓	shortest_palindrome("aacecaaa")अपेक्षित "aaacecaaa"	3 ms
  ✗	shortest_palindrome("abcd")अपेक्षित "dcbabcd"प्राप्त "cbaabcd"	2 ms
  ✓	shortest_palindrome("")अपेक्षित ""	1 ms

  ✓ 3 ms✓ 1 ms✗ गलत उत्तर✓ 4 ms✗ गलत उत्तर✗ गलत उत्तर✗ गलत उत्तर✓ 5 ms✗ गलत उत्तर⏱ गलत उत्तर⏱ गलत उत्तर⏱ गलत उत्तर
  कोड

  /**
   * @param {string} s
   * @returns {string}
   */
  function shortest_palindrome(s) {
      if (s.length === 0) return "";
      
      // Create the combined string: s + '#' + reverse(s)
      let rev = s.split('').reverse().join('');
      let combined = s + '#' + rev;
      
      // Compute the KMP failure function (longest proper prefix which is also suffix)
      let lps = new Array(combined.length).fill(0);
      
      for (let i = 1; i < combined.length; i++) {
          let j = lps[i - 1];
          
          while (j > 0 && combined[i] !== combined[j]) {
              j = lps[j - 1];
          }
          
          if (combined[i] === combined[j]) {
              j++;
          }
          
          lps[i] = j;
      }
      
      // The last value in lps tells us the longest prefix of s that matches a suffix of rev
      // This is the longest palindromic prefix of s
      let longestPrefixLen = lps[combined.length - 1];
      
      // The characters we need to prepend are the remaining part of rev
      let toPrepend = rev.substring(longestPrefixLen);
      
      return toPrepend + s;
  }

  दूसरा प्रयास

  हल किया गया · 15 में से 15 टेस्ट्स पासजवाब का समय 4.2 s · $0.0003

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

  ✓	shortest_palindrome("aacecaaa")अपेक्षित "aaacecaaa"	1 ms
  ✓	shortest_palindrome("abcd")अपेक्षित "dcbabcd"	<1 ms
  ✓	shortest_palindrome("")अपेक्षित ""	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 175 ms⏱ 41 ms⏱ 156 ms

  कोड

  /**
   * @param {string} s
   * @returns {string}
   */
  function shortest_palindrome(s) {
      if (s.length === 0) return "";
      
      // Build the LPS array for s + '#' + reverse(s)
      let rev = s.split('').reverse().join('');
      let combined = s + '#' + rev;
      
      // Compute KMP failure function (LPS array)
      let lps = new Array(combined.length).fill(0);
      
      for (let i = 1; i < combined.length; i++) {
          let j = lps[i - 1];
          
          while (j > 0 && combined[i] !== combined[j]) {
              j = lps[j - 1];
          }
          
          if (combined[i] === combined[j]) {
              j++;
          }
          
          lps[i] = j;
      }
      
      // The last value in lps gives us the length of the longest prefix of s
      // that matches a suffix of rev (which is the longest palindromic prefix of s)
      let longestPrefixLen = lps[combined.length - 1];
      
      // The characters we need to prepend are the remaining part of the reversed string
      // that doesn't overlap with the palindromic prefix
      let toPrepend = rev.substring(0, s.length - longestPrefixLen);
      
      return toPrepend + s;
  }

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