The goal is to find the longest substring that exists at both the start and end of the string, but it must not be the entire string itself. In the brute force approach, we try all possible lengths of such substrings, beginning with the longest possible and gradually reducing the size. At each step, we compare a prefix from the beginning with a suffix from the end. As soon as we find a match, we return it, since we are checking from longest to shortest. This method is simple but not optimal for very large strings.

Check for every possible substring starting from the beginning of the string.
For each such substring, check if the same substring also appears at the end of the string.
Start checking from the longest possible substring and move to shorter ones.
Return the first substring that appears at both the start and end.
If no such substring exists, return an empty result.

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find the longest happy prefix
    string longestPrefix(string s) {
        int n = s.size();

        // Loop through all possible prefix-suffix lengths
        for (int len = n - 1; len > 0; len--) {
            // Compare prefix and suffix of current length
            if (s.substr(0, len) == s.substr(n - len, len)) {
                return s.substr(0, len);
            }
        }

        // Return empty string if no happy prefix found
        return "";
    }
};

int main() {
    Solution sol;
    string s = "levellevel";
    cout << sol.longestPrefix(s) << endl;
    return 0;
}