Longest happy prefix

Strings (Advanced Algo) Advanced Problems (Less asked) Hard

Given a string s, return the longest happy prefix of s. A happy prefix is a string that is both a proper prefix and a proper suffix.

If no such prefix exists, return an empty string "".

Examples:

Input: s = "ababab"

Output: "abab"

Explanation: "abab" is the longest prefix which is also suffix. They can overlap in the original string.

Input: s = "aaaa"

Output: "aaa"

Explanation: "aaa" is the longest prefix which is also a suffix in the string "aaaa".

Input: s = "abc"

Constraints

1 <= s.length <= 10⁴

Hints

"Compute the LPS Array: The LPS array for s stores the length of the longest prefix that is also a suffix for each prefix of s. The last value in LPS gives the length of the longest happy prefix."
Extract the happy prefix: If lps[-1] > 0, return s[:lps[-1]]. Otherwise, return """".

Company Tags

Wayfair Intel American Express Databricks Epic Games Western Digital Mastercard Etsy PayPal McKinsey & Company Dropbox Shopify Texas Instruments KPMG JPMorgan Chase Target ARM Red Hat Electronic Arts Philips Healthcare Rockstar Games Cloudflare Docker Square Reddit Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/Ftr7ZSTBrRx/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Striver and the team have worked tirelessly over the past few days to bring this to you. Please bear with us a little more as we finalize everything.

Code

✅ Testcase

Input: {'s': 'ababab'}

Expected:
abab

Actual: -

Time: - sec

Status: Waiting

Problem List

Longest happy prefix

Examples:

Constraints

Hints

Company Tags

Editorial

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts