2
\$\begingroup\$

My code is a mix-up between dynamic programming with the HashMap and brute force with the way I reach out the results and substring. I don't know how to optimize my algorithm without googling and looking for already solved solutions with different approaches.

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() > 1000) return "";
        if (s.length() == 0) return "";
        HashSet<String> hs = new HashSet<>();
        int size = 1;
        String longest = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i; j < s.length() - 1; j++)
            {
                String ss = s.substring(i, j+2);
                int ssl = ss.length();
                if (hs.contains(ss))
                {
                    if (ssl > size) {
                        size = ssl;
                        longest = ss;
                    }
                }
                else{
                    if (isPalindrome(ss)){
                        hs.add(ss);
                        if (ssl > size) {
                            size = ssl;
                            longest = ss;
                        }
                    } 
                }
            }
        }
        return longest;
    }

    public boolean isPalindrome(String s) {
        int j = s.length() - 1;
        int i = 0;
        while (i < j){
            if (s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

The webpage where this problem is posted says the max size of the string can be 1000. However if a string of that size is the input the algorithm takes 200-210 ms to execute and return the substring.

I'm 100% sure it works, but it's slow.

\$\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.