Longest happy prefix

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

This type of problem is prevalent in the development of algorithms used in data compression, pattern recognition, and string matching
In the software industry, particularly in building search engines or plagiarism detectors, a common task is to find repeated strings or patterns
A real-world example is the KMP (Knuth-Morris-Pratt) algorithm, often used in the UNIX grep command, that searches for occurrences of a word within a main text string
This algorithm leverages the idea of happy prefixes to avoid backtracking - thus speeding up the search process

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