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 string static 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.