# Existence of a Substring in a String and Its Reverse
**Difficulty:** EASY
[External](https://leetcode.com/problems/existence-of-a-substring-in-a-string-and-its-reverse)
Canonical: https://scaleengineer.com/dsa/problems/existence-of-a-substring-in-a-string-and-its-reverse
**Data structures:** Hash Table, String
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
Given astring `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.

# Approaches
## Brute Force with Explicit Reverse
This approach directly translates the problem statement into code. It first computes the reverse of the input string `s`. Then, it iterates through all possible substrings of length 2 from the original string `s`. For each of these substrings, it checks if the substring exists within the reversed string. If a match is found, it immediately returns `true`. If the loop completes without finding any such substring, it means none exist, and the function returns `false`.
**Time:** O(N^2), where N is the length of the string. Reversing the string takes `O(N)`. The main loop runs `N-1` times. Inside the loop, `substring()` takes constant time (for length 2), but `String.contains()` takes `O(N)` time in the worst case. This leads to a total time complexity of `O(N) + (N-1)*O(N)`, which simplifies to `O(N^2)`. · **Space:** O(N), where N is the length of the string `s`. This space is required to store the reversed string.
**Pros:** Simple to understand and implement.; Directly follows the problem description.
**Cons:** Inefficient time complexity, making it slow for large strings.; Uses extra space proportional to the string length.
### Explanation
The core idea is to have both the original string and its reverse available. We generate all length-2 substrings from the original string one by one and perform a search for each of them in the reversed string. The first one we find satisfies the condition, and we can stop. While simple, the repeated searching within the reversed string for each substring makes this approach computationally expensive.

```java
class Solution {
    public boolean isSubstringPresent(String s) {
        StringBuilder sb = new StringBuilder(s);
        String reversedS = sb.reverse().toString();
        for (int i = 0; i < s.length() - 1; i++) {
            String sub = s.substring(i, i + 2);
            if (reversedS.contains(sub)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Create a new string `reversedS` by reversing the input string `s`.
*   Loop with an index `i` from `0` to `s.length() - 2`.
*   In each iteration, extract the substring of length 2 starting at `i`, let's call it `sub`. `sub = s.substring(i, i + 2)`.
*   Check if `reversedS` contains `sub` using the built-in `contains` method.
*   If it does, a valid substring has been found. Return `true`.
*   If the loop finishes without returning, it means no such substring was found. Return `false`.

## Optimized Brute Force with Nested Loops
This approach is based on a key insight: a substring `sub` exists in `reverse(s)` if and only if `reverse(sub)` exists in `s`. Therefore, the problem reduces to finding if any length-2 substring `s[i:i+2]` has its reverse, `s[i+1]s[i]`, also present as a substring somewhere in `s`. This can be checked using nested loops. The outer loop picks a substring, and the inner loop searches for its reverse. This avoids the need to create the entire reversed string, saving space compared to the first approach.
**Time:** O(N^2), where N is the length of the string. The two nested loops each run up to `N-1` times, leading to a quadratic time complexity. · **Space:** O(1), as we are only using a few variables to store characters and indices, not creating any new data structures that scale with the input size.
**Pros:** Very space-efficient, using constant extra space.; Avoids creating a new reversed string object.
**Cons:** The time complexity is quadratic, which is inefficient for large inputs.
### Explanation
By using this logical equivalence, we eliminate the need for an explicit `O(N)` space to store the reversed string. We iterate through each possible length-2 substring with an outer loop. For each such substring, we use an inner loop to scan the entire string again, looking for a substring that is its exact reverse. This trades the space for time, resulting in a space-efficient but time-intensive solution.

```java
class Solution {
    public boolean isSubstringPresent(String s) {
        int n = s.length();
        if (n < 2) {
            return false;
        }
        for (int i = 0; i < n - 1; i++) {
            char c1 = s.charAt(i);
            char c2 = s.charAt(i + 1);
            // Now search for the reversed substring "c2c1"
            for (int j = 0; j < n - 1; j++) {
                if (s.charAt(j) == c2 && s.charAt(j + 1) == c1) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   Loop with an index `i` from `0` to `s.length() - 2` to select the first character of a potential substring from `s`.
*   This substring is `s[i:i+2]`.
*   Its reverse is formed by the characters `s[i+1]` and `s[i]`.
*   Loop with an index `j` from `0` to `s.length() - 2` to search for this reversed substring within `s`.
*   Check if `s.charAt(j) == s.charAt(i + 1)` and `s.charAt(j + 1) == s.charAt(i)`.
*   If the condition is met, it means the substring at `j` is the reverse of the substring at `i`. Return `true`.
*   If the loops complete without finding a match, return `false`.

## Single Pass with a HashSet
This is the most efficient approach in terms of time complexity. It also leverages the property that we are looking for a substring `sub` whose reverse `rev(sub)` is also a substring of `s`. To avoid the `O(N)` search time of the previous approaches, we use a `HashSet` to store the substrings we've seen. A `HashSet` provides average `O(1)` time complexity for insertions and lookups. By iterating through the string just once, we can check for the existence of the reversed pair in near-constant time, leading to an overall linear time solution.
**Time:** O(N), where N is the length of the string. We iterate through the string once. Inside the loop, substring creation, reversal, and HashSet operations (add, contains) take constant time on average because the substring length is fixed at 2. · **Space:** O(K), where K is the number of unique substrings of length 2. Since the alphabet is lowercase English letters, K is at most 26*26 = 676. Thus, the space is constant, O(1). If the alphabet were unbounded, it would be O(N).
**Pros:** Optimal time complexity of O(N).; Conceptually clean, trading space for a significant gain in time.
**Cons:** Uses extra space for the HashSet. For very large alphabets and strings, this could be significant, but for this problem's constraints, it's minimal.
### Explanation
We process the string from left to right. For each length-2 substring, we check two conditions: 1) Is its reverse already in our set of seen substrings? This handles cases like `"ab...ba"`. 2) Is the substring itself a palindrome (like `"ee"`)? If a palindromic substring exists, it is present in `s`, and its reverse (which is itself) is also present in `s`, satisfying the condition. If either check passes, we return `true`. Otherwise, we add the current substring to the set and continue. This single pass is sufficient to find any such pair.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isSubstringPresent(String s) {
        if (s.length() < 2) {
            return false;
        }
        Set<String> seen = new HashSet<>();
        for (int i = 0; i < s.length() - 1; i++) {
            String sub = s.substring(i, i + 2);
            String revSub = new StringBuilder(sub).reverse().toString();

            if (sub.equals(revSub)) {
                return true; // Palindromic substring found
            }
            if (seen.contains(revSub)) {
                return true; // Found a substring whose reverse appeared earlier
            }
            seen.add(sub);
        }
        return false;
    }
}
```
### Algorithm
*   Create a `HashSet` to store representations of 2-character substrings encountered so far.
*   Iterate through the string `s` from `i = 0` to `s.length() - 2`.
*   For each `i`, get the current substring `sub = s.substring(i, i + 2)`.
*   Also, form its reverse, `revSub`.
*   Check if `revSub` is already present in the `HashSet`. If yes, a match is found, return `true`.
*   Also, check if `sub` is a palindrome (i.e., `sub.equals(revSub)`). If it is, a match is found, return `true`.
*   Add the current `sub` to the `HashSet` to be checked against in future iterations.
*   If the loop completes, no match was found, so return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isSubstringPresent(String s) {
    boolean[][] st = new boolean[26][26];
    int n = s.length();
    for (int i = 0; i < n - 1; ++i) {
      st[s.charAt(i + 1) - 'a'][s.charAt(i) - 'a'] = true;
    }
    for (int i = 0; i < n - 1; ++i) {
      if (st[s.charAt(i) - 'a'][s.charAt(i + 1) - 'a']) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isSubstringPresent(string s) {
    bool st[26][26]{};
    int n = s.size();
    for (int i = 0; i < n - 1; ++i) {
      st[s[i + 1] - 'a'][s[i] - 'a'] = true;
    }
    for (int i = 0; i < n - 1; ++i) {
      if (st[s[i] - 'a'][s[i + 1] - 'a']) {
        return true;
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def isSubstringPresent(self, s: str) -> bool: st = {(a, b) for a, b in pairwise(s[:: - 1])} return any((a, b) in st for a, b in pairwise(s))

```