Jobs

Interviews

Discussions

Existence of a Substring in a String and Its Reverse

Easy

Rubrik

6 views

Topics:

StringsTwo PointersSliding Windows

Given a string s, find any substring of length 2 which is also present in the reverse of s.

Return true if such a substring exists, and false otherwise.

Example 1:

Input: s = "leetcode"

Output: true

Explanation: Substring "ee" is of length 2 which is also present in reverse(s) == "edocteel".

Example 2:

Input: s = "abcba"

Output: true

Explanation: All of the substrings of length 2 "ab", "bc", "cb", "ba" are also present in reverse(s) == "abcba".

Example 3:

Input: s = "abcd"

Output: false

Explanation: There is no substring of length 2 in s, which is also present in the reverse of s.

Constraints:

1 <= s.length <= 100
s consists only of lowercase English letters.

Try coding it in LeetCode

Existence of a Substring in a String and Its Reverse

Easy

Rubrik

6 views

Topics:

StringsTwo PointersSliding Windows

Given a string s, find any substring of length 2 which is also present in the reverse of s.

Return true if such a substring exists, and false otherwise.

Example 1:

Input: s = "leetcode"

Output: true

Explanation: Substring "ee" is of length 2 which is also present in reverse(s) == "edocteel".

Example 2:

Input: s = "abcba"

Output: true

Explanation: All of the substrings of length 2 "ab", "bc", "cb", "ba" are also present in reverse(s) == "abcba".

Example 3:

Input: s = "abcd"

Output: false

Explanation: There is no substring of length 2 in s, which is also present in the reverse of s.

Constraints:

1 <= s.length <= 100
s consists only of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can either string1 or string2 be null or empty strings? If so, what should the function return?
Are the strings case-sensitive, or should the substring check be case-insensitive?
What is the maximum length of string1 and string2?
By 'substring', do you mean a contiguous sequence of characters, or can there be gaps?
If string2 (or its reverse) appears multiple times as a substring in string1, does the function still return true?

Brute Force Solution

Approach

The brute force approach to finding if a string contains a substring and its reverse is very straightforward. We essentially check every possible substring within the main string, and then see if the reversed version of that substring also exists somewhere in the main string. We do this exhaustively until we either find a match or have checked every single possibility.

Here's how the algorithm would work step-by-step:

Consider every possible piece of the main string as a potential substring. Start with pieces of length one, then length two, and so on, up to the full length of the main string.
For each of these potential substrings, make a reversed copy of it.
Then, look through the main string to see if that reversed copy exists anywhere inside it.
If you find the reversed copy, you've found a match! You know that both the original substring and its reverse exist in the main string.
If you've gone through all possible substrings and haven't found a match, then no such substring and its reverse exist in the main string.

Code Implementation

def find_substring_and_reverse(main_string):
    string_length = len(main_string)

    for substring_length in range(1, string_length + 1):
        for i in range(string_length - substring_length + 1):

            substring = main_string[i:i + substring_length]

            reversed_substring = substring[::-1]

            # Check if the reversed substring exists in the main string
            if reversed_substring in main_string:

                # If it does, we found a match
                return True

    # If loop completes, no match was found.
    return False

Big(O) Analysis

Time Complexity

O(n^3) – The outermost loop iterates through all possible substring lengths, from 1 to n, where n is the length of the input string. For each substring length, we iterate through all possible starting positions of the substring within the string, giving us another loop dependent on n. Inside these loops, we reverse the substring which takes O(n) time in the worst case where the substring length is approaching n. Finally we search for the reversed substring within the original string which takes O(n) time. Therefore, the time complexity is O(n * n * n) which simplifies to O(n^3).

Space Complexity

O(N) – The provided algorithm generates substrings of varying lengths from the main string. For each substring, it creates a reversed copy. In the worst-case scenario, a substring can be of length N (where N is the length of the main string), and its reversed copy would also be of length N. Therefore, the algorithm uses auxiliary space to store the reversed copy of the substring, leading to a space complexity of O(N).

Optimal Solution

Approach

The efficient way to solve this problem involves cleverly looking for a string or its reversed version. Instead of checking every possible section of the main string, we use a fast searching algorithm to quickly locate either the original string or its flipped counterpart.

Here's how the algorithm would work step-by-step:

First, reverse the string you are looking for, so you have both the original and the reversed version.
Then, use an efficient search tool to find the original string within the larger string.
If you don't find the original string, use the same efficient search tool to look for the reversed string within the larger string.
If either the original or reversed string is found, then the answer is yes. Otherwise, the answer is no.

Code Implementation

def find_substring_or_reverse(main_string, substring_to_find):
    reversed_substring = substring_to_find[::-1]

    # Search for the original substring.
    if substring_to_find in main_string:
        return True

    # Search for the reversed substring.
    if reversed_substring in main_string:
        return True

    return False

def existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find):
    # Handle edge case of empty substring
    if not substring_to_find:
        return True

    return find_substring_or_reverse(main_string, substring_to_find)

def main():
    main_string = "abcdefg"
    substring_to_find = "bcd"
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcdefg"
    substring_to_find = "gfe"
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcdefg"
    substring_to_find = "xyz"
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcdefg"
    substring_to_find = ""
    # Test with empty substring
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcba"
    substring_to_find = "abc"
    # Testing a palindrome-like case
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity

O(n) – The primary operations involve reversing the search string (complexity dependent on string length but considered constant relative to the main string), and then performing at most two substring searches using an efficient algorithm. Assuming an efficient algorithm like the Knuth-Morris-Pratt (KMP) or Boyer-Moore algorithm is used for substring search, each search has a time complexity of O(n), where n is the length of the main string. Since we perform at most two such searches, the overall time complexity remains O(n). Reversing the string to be searched is of length m where m is the length of the search string; we assume m << n. Therefore, time to reverse is considered O(1) relative to n.

Space Complexity

O(M) – The primary auxiliary space usage comes from reversing the string we are searching for, which creates a new string of length M, where M is the length of the string being searched for. The string search algorithm itself might use a small constant amount of memory for variables, but reversing the string dominates the space usage. Thus, the auxiliary space complexity is determined by the reversed string's storage, which depends directly on the length of the substring to be searched, giving us a space complexity of O(M).

Edge Cases

Case	How to Handle
string1 or string2 is null	Return false immediately since null strings cannot contain substrings.
string1 or string2 is empty	Return true if string2 is empty and string1 is not null, otherwise return false.
string2 is longer than string1	Return false immediately, since a longer string cannot be a substring of a shorter string.
string1 and string2 are identical	Return true immediately, since the string is a substring of itself.
string1 contains multiple overlapping occurrences of string2 or its reverse	The algorithm should still correctly return true as it only needs to find one occurrence.
string2 contains special characters or unicode	The substring search algorithm should work correctly regardless of special characters as it is a character-by-character comparison.
Very long strings to test for performance	Ensure the chosen algorithm (e.g., using `string.contains()` or similar) is efficient for large string lengths to avoid timeout issues.
string2 is the reverse of string1	The reverse check should catch this case and return true.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can either string1 or string2 be null or empty strings? If so, what should the function return?
Are the strings case-sensitive, or should the substring check be case-insensitive?
What is the maximum length of string1 and string2?
By 'substring', do you mean a contiguous sequence of characters, or can there be gaps?
If string2 (or its reverse) appears multiple times as a substring in string1, does the function still return true?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider every possible piece of the main string as a potential substring. Start with pieces of length one, then length two, and so on, up to the full length of the main string.
For each of these potential substrings, make a reversed copy of it.
Then, look through the main string to see if that reversed copy exists anywhere inside it.
If you find the reversed copy, you've found a match! You know that both the original substring and its reverse exist in the main string.
If you've gone through all possible substrings and haven't found a match, then no such substring and its reverse exist in the main string.

Code Implementation

def find_substring_and_reverse(main_string):
    string_length = len(main_string)

    for substring_length in range(1, string_length + 1):
        for i in range(string_length - substring_length + 1):

            substring = main_string[i:i + substring_length]

            reversed_substring = substring[::-1]

            # Check if the reversed substring exists in the main string
            if reversed_substring in main_string:

                # If it does, we found a match
                return True

    # If loop completes, no match was found.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, reverse the string you are looking for, so you have both the original and the reversed version.
Then, use an efficient search tool to find the original string within the larger string.
If you don't find the original string, use the same efficient search tool to look for the reversed string within the larger string.
If either the original or reversed string is found, then the answer is yes. Otherwise, the answer is no.

Code Implementation

def find_substring_or_reverse(main_string, substring_to_find):
    reversed_substring = substring_to_find[::-1]

    # Search for the original substring.
    if substring_to_find in main_string:
        return True

    # Search for the reversed substring.
    if reversed_substring in main_string:
        return True

    return False

def existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find):
    # Handle edge case of empty substring
    if not substring_to_find:
        return True

    return find_substring_or_reverse(main_string, substring_to_find)

def main():
    main_string = "abcdefg"
    substring_to_find = "bcd"
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcdefg"
    substring_to_find = "gfe"
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcdefg"
    substring_to_find = "xyz"
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcdefg"
    substring_to_find = ""
    # Test with empty substring
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

    main_string = "abcba"
    substring_to_find = "abc"
    # Testing a palindrome-like case
    result = existence_of_substring_in_a_string_and_its_reverse(main_string, substring_to_find)
    print(f"Main string: {main_string}, Substring: {substring_to_find}, Result: {result}")

if __name__ == "__main__":
    main()

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
string1 or string2 is null	Return false immediately since null strings cannot contain substrings.
string1 or string2 is empty	Return true if string2 is empty and string1 is not null, otherwise return false.
string2 is longer than string1	Return false immediately, since a longer string cannot be a substring of a shorter string.
string1 and string2 are identical	Return true immediately, since the string is a substring of itself.
string1 contains multiple overlapping occurrences of string2 or its reverse	The algorithm should still correctly return true as it only needs to find one occurrence.
string2 contains special characters or unicode	The substring search algorithm should work correctly regardless of special characters as it is a character-by-character comparison.
Very long strings to test for performance	Ensure the chosen algorithm (e.g., using `string.contains()` or similar) is efficient for large string lengths to avoid timeout issues.
string2 is the reverse of string1	The reverse check should catch this case and return true.