1
\$\begingroup\$

After getting comments on my previous implementation, I have tried to implement with DP. But without using matrix. I am not doing any boundary checks on the string just wanted to see if I am missing anything in this implementation.

Approach
I am using Set to store existing palindromes. First I add all letters which are palindrome by itself and then i add palindromes of size 2. Then I start with size 3. I check if the substring of current size is already been tested as palindrome or not, if it is, then i check the beginning and end character of the current string if they matches, i add them to the set and move on

My main aim was to get \$O(n^2)\$ by thinking and coding myself rather than looking at existing solutions. Normally, a 2D matrix is used when programming a DP but I used a set because to me it looked more intuitive and less complex.

public static String lpsMap(String str) {
    int maxSize = 0;
    String longestP = null;
    Set<String> map = new HashSet<>();

    for (char ch : str.toCharArray()) {
        map.add(String.valueOf(ch));
    }

    for (int i = 0; i < str.length() - 1; i++) {
        if (str.charAt(i) == str.charAt(i + 1)) {
            map.add(str.substring(i, i + 2));
        }
    }

    for (int len = 3; len <= str.length(); len++) {
        for (int index = 0; index < str.length() - len + 1; index++) {
            int endIndex = index + len;
            String existingP = str.substring(index + 1, endIndex - 1);
            if (map.contains(existingP)) {
                if (str.charAt(index) == str.charAt(endIndex - 1)) {
                    String currentP = str.substring(index, endIndex);
                    map.add(currentP);
                    if (currentP.length() > maxSize) {
                        maxSize = currentP.length();
                        longestP = currentP;
                    }
                }
            }
        }
    }

    return longestP;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.