In this article, let's solve the leetcode Longest Happy Prefix problem.

This problem is very easy to understand. A happy prefix is a prefix and also is a suffix of a string. For example, if we have a string level, first calculate the prefix: l, le, lev, leve, then calculate the suffix l, el, vel, evel. And we need to find the longest common one, which is l.

We can use two pointers and a temporary array to solve this problem. Let's use an example to show the process.

Say we have a string aabaabaaa, initialize an array with the same length [] and two pointer i = 1, j = 0.

Step 1: initial

 j i
 a a b a a b a a a
[0                ]

Step 2: compare s[i] and s[j], its equal, move j, fill array with j , and move i

   j i
 a a b a a b a a a
[0 1              ]

Step 3: compare again, its not equal, move j to j = array[j-1]

 j   i
 a a b a a b a a a
[0 1              ]

Step 4: compare again, not equal and j is 0, then fill array with 0, and move i

 j     i
 a a b a a b a a a
[0 1 0            ]

Step 5: compare again, equal, same process with step 2

   j     i
 a a b a a b a a a
[0 1 0 1          ]

Step 6: compare again, equal, same process with step 2

     j     i
 a a b a a b a a a
[0 1 0 1 2        ]

Step 7: compare again, equal, same process with step 2

       j     i
 a a b a a b a a a
[0 1 0 1 2 3      ]

Step 8: compare again, equal, same process with step 2

         j     i
 a a b a a b a a a
[0 1 0 1 2 3 4    ]

Step 9: compare again, equal, same process with step 2

           j     i
 a a b a a b a a a
[0 1 0 1 2 3 4 5  ]

Step 10: compare again, not equal, same process with step 3, move j to j = array[j-1]

     j           i
 a a b a a b a a a
[0 1 0 1 2 3 4 5  ]

Step 11: compare again, not equal, same process with step 3

   j             i
 a a b a a b a a a
[0 1 0 1 2 3 4 5  ]

Step 12: compare again, equal, same process with step 2

     j             i
 a a b a a b a a a
[0 1 0 1 2 3 4 5 2]

So, loop is done. As you can see, every step we calcuate the longest happy prefix of the current string. For every iteration, we don't need to calculate from the beginning, we can use the previous result to calculate current one. So time complexity is O(n).

Let implement this process in code.

function longestPrefix(s: string): string {
    let i = 1;
    let j = 0;
    let lps = Array.from({ length: s.length }, _ => 0);
    while (i < s.length) {
        if (s.charAt(i) === s.charAt(j)) {
            lps[i++] = ++j;
        } else {
            if (j === 0) {
                lps[i++] = 0;
            } else {
                j = lps[j - 1];
            }
        }
    }
    return s.slice(0, j)
};