# Existence of a Substring in a String and its Reverse in Java

In this tutorial, we are going to know about existence of a substring in a string and its reverse in Java. Given a string S and an array of indices A[], the task is to reverse the substrings of the given string according to the given Array of indices and also in a given 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 = “Repaper”

Output: true

Explanation: All of the substrings of length 2 “re”, “ep”, “pa”, “ap”, “pe”, “er” are also present in reverse(s) == “repaper”.

Example 2:

Input: s = “efghij”

Output: false

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

Example 3:

Input: S = “civic”

Output: true

Explanation: All of the substrings of length 2 “ci”, “iv”, “vi”, “ic” are also present in reverse(s) == “civic”.

## Naïve approach:

Step 1: At first, use a StringBuilder and its reverse() function, SubstringPresent() reverses the given string s.

Step 2: Begin with the second character, to iterate through the original string s.

Step 3: Determine whether the reversed string has a substring made of the current character joined to the preceding character from the original string.

Step 4: Return true, signifying that a substring exists in reverse order.

Step 5: Return false if no such substring is found during the loop.

Filename: SubString.java

`public class SubString{public boolean isSubstringPresent(String str){String reversed = new StringBuilder(str).reverse().toString();        for(int r = 1; r < str.length(); r++)        {            if (reversed.contains(String.valueOf(str.charAt(r - 1)) + String.valueOf(str.charAt(r))))           {                return true;            }        }        return false;    }    public static void main(String[] args)     {        SubString subString = new SubString();        String testString = "hello";        boolean isSubstringFound = subString.isSubstringPresent(testString);        if (isSubstringFound)       {            System.out.println("A substring exists in reverse order within the string.");        }         else         {            System.out.println("No such substring exists in reverse order within the string.");        }    }}`

Output:

`A substring exists in reverse order within the string.`

Time Complexity: The time complexity of a program is O(n ^ 2).

Space Complexity: The space complexity of a program is O(n).

## Approach 1: Using Sorted Index Substring Reversal

### ALGORITHM:

Step 1: Arrange the Array of Indices.

Step 2: For every index in the provided array, extract the substring that was created as follows:

Step 2.1: The substring created for the first position in the array A will be from index 0 to A[0] (exclusive) of the supplied string, or [0, A[0]).

Step 2.2: The substring created for each other index in the array A (apart from the last) will be from index A[i] to A[i+1] (exclusive) of the supplied text, or [A[i], A[i+1])

Step 2.2: The last index in the array A will result in a substring that extends from index A[i] to L (inclusive), where L is the string's length, or [A[i], L].

Step 3: Every substring in the provided string should be reversed.

Filename: ReverseString.java

`public class ReverseString{static String str;// Reverse a String function static void reverseAString(int x, int y){            int length = y - x;            // Change the character by beginning at two corners.            for (int a = 0; a < length / 2; a++)            {                        str = swap(a + x, length - a - 1 + x);            }}// Use the given array of indices, this function reverses the stringstatic void reverseAString(int K[], int length){            reverseAString(0, K[0]);            // Reverse the String for K[a] to K[a+1]            for (int a = 1; a < length; a++)                        reverseAString(K[a - 1], K[a]);            // Reverse String for K[length-1] to length            reverseAString(K[length - 1], str.length());}static String swap(int a, int b){            char characters[] = str.toCharArray();            char temp = characters[a];            characters[a] = characters[b];            characters[b] = temp;            return String.valueOf(characters);}public static void main(String[] args){            str = "racecara";            int K[] = { 4, 6, 8 };            int length = K.length;            reverseAString(K, length);            System.out.print(str);}}`

Output:

`ecaracar`

Complexity Analysis:

Time Complexity: The time complexity of a program is O(l * n) for sorting.
Space Complexity: The space complexity of a program is O(1) for prefix sum.