algoadvance

Leetcode 3083. Existence of a Substring in a String and Its Reverse

Problem Statement

Given two strings s1 and s2, write a function to check if there exists a substring in s1 that is equal to s2 or its reverse. You need to return true if such a substring exists in s1; otherwise, return false.

Clarifying Questions

  1. Input Validations:
    • Can s1 and s2 be empty? If so, what should be the output?
    • Are we considering only alphabetic characters, or could there be numbers and special characters as well?
  2. Case Sensitivity:
    • Do we treat uppercase and lowercase characters as equal or different?
  3. Constraints:
    • What is the maximum length of s1 and s2?
    • Any restrictions on time or space complexity?

Strategy

  1. Reverse s2: Store the reverse of s2.
  2. Check Substring:
    • Iterate through s1 to check if s2 or its reverse appears as substrings.
  3. Optimized Approach:
    • Use the contains method provided by Java’s String class for efficient substring searching.

Time Complexity

  1. String Reverse: O(n) for reversing s2 where n is the length of s2.
  2. Substring Search: O(m * n) in the worst case, where m is the length of s1 and n is the length of s2. However, the average complexity of the .contains method tends to be more efficient due to internal optimizations.

Code

public class SubstringReverseCheck {
    public boolean checkSubstring(String s1, String s2) {
        if (s1 == null || s2 == null) return false;
        
        String s2Reversed = new StringBuilder(s2).reverse().toString();
        
        boolean containsS2 = s1.contains(s2);
        boolean containsS2Reversed = s1.contains(s2Reversed);
        
        return containsS2 || containsS2Reversed;
    }

    public static void main(String[] args) {
        SubstringReverseCheck checker = new SubstringReverseCheck();
        
        // Test cases
        System.out.println(checker.checkSubstring("abcdefg", "cde")); // true
        System.out.println(checker.checkSubstring("abcdefg", "edc")); // true
        System.out.println(checker.checkSubstring("abcdefg", "xyz")); // false
        System.out.println(checker.checkSubstring("abcdefg", "")); // true, empty is considered a substring
    }
}

Explanation

  1. StringBuilder Reverse Method: Reverses s2.
  2. String contains Method: Searches for the presence of s2 or its reverse in s1.
  3. Null Checks: Ensures no null pointer exceptions occur.
  4. Return Statement: Returns true if either s2 or its reverse is found in s1.

This code efficiently uses built-in Java methods to achieve the desired functionality, balancing readability and performance.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI