How to keep the time low when submitting question on coding Platforms Like Leetcode?

[Omkumar2003]

Body

So I was working on the Longest Palindromic Substring problem, and I thought — let's keep the same O(n^3) logic, but just change the way it’s implemented, not the core idea.

I heard from someone that you should warm up the JVM with small dummy inputs so that it can optimize and run faster later.

Wherever possible, use pointers instead of creating new objects (like using substring).
Also, regarding String vs StringBuilder vs char[] — using a char array is usually the fastest.

Are there any other ways to make a program faster, like some competitive programming tips?

So I came up with the following solution, which is quite fast and still O(n^3)

class Solution {
    static{
        for(int i =0;i<400;i++){
            longestPalindrome("a");
        }
    }

    public static boolean isPal(char[] s,int f, int l){
        // int f =0;
        // int l =s.length()-1;
        while (f<l){
            if(s[f]!=s[l]) return false;
            f++;
            l--;
        }
        return true;
    }

    public static String longestPalindrome(String s) {
        char[] arr = s.toCharArray();
        // String ans ="";
        // for(int i =0;i<s.length();i++){
        //     for(int j=s.length()-1;j>=i;j--){
        //         String temp= s.substring(i,j+1);
        //         if(temp.length()<=ans.length()) break;
        //         if(isPal(temp) && ans.length()<temp.length()){
        //             ans=temp;
        //         }
        //     }
        // }
        int bestL = 0, bestR = 0;
        om:
        for(int j=arr.length;j>0;j--){
            int win =j;
            for(int i =0;i<arr.length-win+1;i++){
                // String temp= s.substring(i,i+win);
                int temp = i+win-1;
                if(isPal(arr,i,temp)){
                     bestL = i;
                    bestR = temp;
                    // ans = temp;
                    break om;
                }
            }
        }
        
        return s.substring(bestL, bestR + 1);
        
    }
}

Guidelines

• I have read and understood this category's guidelines before making this post.

[conorheffron]

@Omkumar2003

• HackerRank, CodeSignal, Codility, LeetCode, NeetCode & more are good sites for practice courses & sometimes require subscriptions or purchase to view common questions per tech company (good if you want to prepare for interview with specific FAANG company etc. circa 20/30 quid).
• There are also co-pilot tools for your preferred IDE (IDEA products / VS code etc) to help drive developer efficiency & to assist in the learning process. In addition, MOOCs are a great resource and there are many with online IDEs, compilers/ runtime envs, interactive exercises etc. See list:
  • https://en.wikipedia.org/wiki/List_of_MOOC_providers
  • https://www.classcentral.com/subject/leetcode
  • https://www.my-mooc.com/en/categorie/programming-languages
  • https://www.edx.org/learn/computer-science?hs_analytics_source=referrals&utm_source=mooc.org&utm_medium=referral&utm_campaign=mooc.org-topics
  • https://www.edx.org/learn/data-science?hs_analytics_source=referrals&utm_source=mooc.org&utm_medium=referral&utm_campaign=mooc.org-topics

Overview

• The code is an implementation of finding the Longest Palindromic Substring in a given string. While it works, it can be optimized for better performance. Below is a cleaned-up and slightly improved version of your code, along with explanations for clarity.

Optimized Code

class Solution {
    public static boolean isPalindrome(char[] s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    public static String longestPalindrome(String s) {
        char[] arr = s.toCharArray();
        int bestL = 0, bestR = 0;

        // Iterate over all possible window sizes
        for (int win = arr.length; win > 0; win--) {
            for (int i = 0; i <= arr.length - win; i++) {
                int temp = i + win - 1;
                if (isPalindrome(arr, i, temp)) {
                    bestL = i;
                    bestR = temp;
                    return s.substring(bestL, bestR + 1); // Return immediately when the longest palindrome is found
                }
            }
        }
        return s.substring(bestL, bestR + 1);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad")); // Example test case
    }
}

Key Improvements

Readability:

• Renamed isPal to isPalindrome for better clarity.
• Added comments to explain the logic.

Efficiency:

• The outer loop iterates over decreasing window sizes (win), ensuring the longest palindrome is found first. This allows for an early return, reducing unnecessary computations.

Removed Unnecessary Code:

• Removed the static block (static {}) as it doesn't contribute to the solution logic.
• Simplified variable names and removed unused variables like om.

Performance Consideration (See more in Complexity Analysis Section)

• This approach has a time complexity of O(n³) due to the nested loops and the palindrome check.
• While it works for small inputs, it can be slow for larger strings.
• For better performance, consider using Dynamic Programming (O(n²)) or Manacher's Algorithm (O(n)).

---

Complexity Analysis & Testing with Mock Data

Time Complexity:

1. The outer loop iterates over all possible window sizes from the length of the string down to 1. This contributes O(n) iterations.
2. The inner loop iterates over all possible starting indices for a given window size, which is proportional to the length of the string. This contributes O(n) iterations.
3. The isPalindrome function checks if a substring is a palindrome, which takes O(k) time, where k is the length of the substring (up to n in the worst case).

Combining these, the overall time complexity is O(n³) in the worst case.

Space Complexity:

1. The space used by the char[] arr is O(n), where n is the length of the input string.
2. No additional data structures are used, so the overall space complexity is O(n).

Re-Optimized Code with Tests

// Updated Code with Error Handling, Test Cases, and Syntax Fixes

class Solution {
    public static boolean isPalindrome(char[] s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    public static String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            throw new IllegalArgumentException("Input string cannot be null or empty.");
        }

        char[] arr = s.toCharArray();
        int bestL = 0, bestR = 0;

        // Iterate over all possible window sizes
        for (int win = arr.length; win > 0; win--) {
            for (int i = 0; i <= arr.length - win; i++) {
                int temp = i + win - 1;
                if (isPalindrome(arr, i, temp)) {
                    bestL = i;
                    bestR = temp;
                    return s.substring(bestL, bestR + 1); // Return immediately when the longest palindrome is found
                }
            }
        }
        return s.substring(bestL, bestR + 1);
    }

    public static void main(String[] args) {
        // Test Cases
        try {
            System.out.println("Test Case 1: " + longestPalindrome("babad")); // Expected: "bab" or "aba"
            System.out.println("Test Case 2: " + longestPalindrome("cbbd"));  // Expected: "bb"
            System.out.println("Test Case 3: " + longestPalindrome("a"));     // Expected: "a"
            System.out.println("Test Case 4: " + longestPalindrome("ac"));    // Expected: "a" or "c"
            System.out.println("Test Case 5: " + longestPalindrome(""));      // Expected: Exception
        } catch (IllegalArgumentException e) {
            System.out.println("Error: " + e.getMessage());
        }
    }
}

Mock Data for Testing

1. Input: "babad"

   • Expected Output: "bab" or "aba"

2. Input: "cbbd"

   • Expected Output: "bb"

3. Input: "a"

   • Expected Output: "a"

4. Input: "ac"

   • Expected Output: "a" or "c"

5. Input: "" (empty string)

   • Expected Output: Exception with message "Input string cannot be null or empty."

---

Code Explanation

This program finds the longest palindromic substring in a given string using a brute-force approach. Here's a detailed explanation:

1. Algorithm:

   • A palindrome is a string that reads the same forward and backward.
   • The algorithm iterates over all possible substrings of the input string, starting with the largest possible substrings and decreasing the size.
   • For each substring, it checks if it is a palindrome using the isPalindrome method.
   • If a palindrome is found, it is stored as the current best result, and the search terminates early since larger substrings are checked first.

2. Steps:

   • Convert the input string into a character array for efficient access.
   • Use nested loops:
     • The outer loop iterates over possible substring lengths (from longest to shortest).
     • The inner loop iterates over starting indices for substrings of the current length.
   • For each substring, check if it is a palindrome using the isPalindrome method.
   • Return the longest palindrome found.

3. Error Handling:

   • The program checks for null or empty input and throws an exception if the input is invalid.

4. Optimization:

   • The algorithm terminates early when the longest palindrome is found, reducing unnecessary computations.

5. Scientific Notation:

   • The brute-force approach has a time complexity of $$O(n^3)$$, where $$n$$ is the length of the input string. This is due to the nested loops and the palindrome check for each substring.

6. Formal Algorithm:

   • Input: A string $$s$$ of length $$n$$.
   • Output: The longest palindromic substring of $$s$$.
   • Steps:
     1. Initialize variables to track the best palindrome's start and end indices.
     2. Iterate over all possible substring lengths (from $$n$$ to 1).
     3. For each length, iterate over all starting indices.
     4. Check if the substring is a palindrome.
     5. If a palindrome is found, update the best indices and terminate the search.
     6. Return the substring corresponding to the best indices.