Given a string str, two characters X and Y. The task is to find the length of the longest substring that starts with X and ends with Y. It is given that there always exists a substring that starts with X and ends with Y.
Examples:
Input: str = “QWERTYASDFZXCV”, X = ‘A’, Y = ‘Z’
Output: 5
Explanation:
The largest substring which start with ‘A’ and end with ‘Z’ = “ASDFZ”.
Size of the substring = 5.
Input: str = “ZABCZ”, X = ‘Z’, Y = ‘Z’
Output: 3
Explanation:
The largest substring which start with ‘Z’ and end with ‘Z’ = “ZABCZ”.
Size of the substring = 5.
Naive Approach: The naive approach is to find all the substrings of the given string out of these find the largest substring which starts with X and ends with Y.
C++
// C++ program for the naive approach#include <bits/stdc++.h>using namespace std;// Function returns length of longest substring starting// with X and ending with Yint longestSubstring(string str, char X, char Y){ int n = str.size(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // is str[i] == X and str[j] == Y then the // substring str[i...j] maybe longest substring // that we required if (str[i] == X && str[j] == Y) { ans = max(ans, j - i + 1); } } } return ans;}// Driver Codeint main(){ // Given string str string str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters char X = 'A', Y = 'Z'; // Function Call cout << longestSubstring(str, X, Y) << "\n"; return 0;}// This code is contributed by ajaymakvana |
Java
// JAVA program for the naive approachimport java.util.*;class GFG { // Function returns length of longest substring starting // with X and ending with Y public static int longestSubstring(String str, char X, char Y) { int n = str.length(); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // is str[i] == X and str[j] == Y then the // substring str[i...j] maybe longest // substring that we required if (str.charAt(i) == X && str.charAt(j) == Y) { ans = Math.max(ans, j - i + 1); } } } return ans; } // Driver Code public static void main(String[] args) { // Given string str String str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters char X = 'A', Y = 'Z'; // Function Call System.out.println(longestSubstring(str, X, Y)); }}// This code is contributed by Taranpreet |
Python3
# Function returns length of longest substring starting# with X and ending with Ydef longest_substring(str, X, Y): n = len(str) ans = 0 for i in range(n): for j in range(i+1, n): # is str[i] == X and str[j] == Y then the # substring str[i...j] maybe longest # substring that we required if str[i] == X and str[j] == Y: ans = max(ans, j - i + 1) return ans# given stringstr = "HASFJGHOGAKZZFEGA"# Starting and Ending charactersX = 'A'Y = 'Z'# Function callprint(longest_substring(str, X, Y)) |
C#
// C# program for the naive approachusing System;public class GFG { // Function returns length of longest substring starting // with X and ending with Y public static int LongestSubstring(string str, char X, char Y) { int n = str.Length; int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // is str[i] == X and str[j] == Y then the // substring str[i...j] maybe longest // substring that we required if (str[i] == X && str[j] == Y) { ans = Math.Max(ans, j - i + 1); } } } return ans; } // Driver Code public static void Main() { // Given string str string str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters char X = 'A', Y = 'Z'; // Function Call Console.WriteLine(LongestSubstring(str, X, Y)); }}//contributed by adityasha4x71 |
Javascript
// Javascript program for the above approach// Function returns length of longest substring starting// with X and ending with Yfunction longest_substring(str, X, Y) { let n = str.length; let ans = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // is str[i] == X and str[j] == Y then the // substring str[i...j] maybe longest // substring that we required if (str[i] == X && str[j] == Y) { ans = Math.max(ans, j - i + 1); } } } return ans;}// given stringlet str = "HASFJGHOGAKZZFEGA";// Starting and Ending characterslet X = 'A';let Y = 'Z';// Function callconsole.log(longest_substring(str, X, Y));// This code is contributed by princekumaras |
Output
12
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimized the above approach, the count of characters between X and Y should be the largest. So, iterate over the string using pointers start and end to find the first occurrence of X from the starting index and the last occurrence of Y from the end. Below are the steps:
- Initialize start = 0 and end = length of string – 1.
- Traverse the string from the beginning and find the first occurrence of character X. Let it be at index xPos.
- Traverse the string from the beginning and find the last occurrence of character Y. Let it be at index yPos.
- The length of the longest substring is given by (yPos – xPos + 1).
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function returns length of longest // substring starting with X and // ending with Y int longestSubstring(string str, char X, char Y) { // Length of string int N = str.length(); int start = 0; int end = N - 1; int xPos = 0; int yPos = 0; // Find the length of the string // starting with X from the beginning while (true) { if (str[start] == X) { xPos = start; break; } start++; } // Find the length of the string // ending with Y from the end while (true) { if (str[end] == Y) { yPos = end; break; } end--; } // Longest substring int length = (yPos - xPos) + 1; // Print the length cout << length; } // Driver Code int main() { // Given string str string str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters char X = 'A', Y = 'Z'; // Function Call longestSubstring(str, X, Y); return 0; } |
Java
// Java program for the above approach class GFG{ // Function returns length of longest // substring starting with X and // ending with Y public static void longestSubstring(String str, char X, char Y) { // Length of string int N = str.length(); int start = 0; int end = N - 1; int xPos = 0; int yPos = 0; // Find the length of the string // starting with X from the beginning while (true) { if (str.charAt(start) == X) { xPos = start; break; } start++; } // Find the length of the string // ending with Y from the end while (true) { if (str.charAt(end) == Y) { yPos = end; break; } end--; } // Longest substring int length = (yPos - xPos) + 1; // Print the length System.out.print(length);} // Driver codepublic static void main(String[] args){ // Given string str String str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters char X = 'A', Y = 'Z'; // Function Call longestSubstring(str, X, Y); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach # Function returns length of longest # substring starting with X and # ending with Y def longestSubstring(str, X, Y): # Length of string N = len(str) start = 0 end = N - 1 xPos = 0 yPos = 0 # Find the length of the string # starting with X from the beginning while (True): if (str[start] == X): xPos = start break start += 1 # Find the length of the string # ending with Y from the end while (True): if (str[end] == Y): yPos = end break end -= 1 # Longest substring length = (yPos - xPos) + 1 # Print the length print(length)# Driver Code if __name__ == "__main__": # Given string str str = "HASFJGHOGAKZZFEGA" # Starting and Ending characters X = 'A' Y = 'Z' # Function Call longestSubstring(str, X, Y) # This code is contributed by sanjoy_62 |
C#
// C# program for the above approach using System;class GFG{ // Function returns length of longest // substring starting with X and // ending with Y static void longestSubstring(string str, char X, char Y) { // Length of string int N = str.Length; int start = 0; int end = N - 1; int xPos = 0; int yPos = 0; // Find the length of the string // starting with X from the beginning while (true) { if (str[start] == X) { xPos = start; break; } start++; } // Find the length of the string // ending with Y from the end while (true) { if (str[end] == Y) { yPos = end; break; } end--; } // Longest substring int length = (yPos - xPos) + 1; // Print the length Console.Write(length);} // Driver codepublic static void Main(){ // Given string str string str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters char X = 'A', Y = 'Z'; // Function call longestSubstring(str, X, Y); }}// This code is contributed by sanjoy_62 |
Javascript
<script> // JavaScript program for the above approach // Function returns length of longest // substring starting with X and // ending with Y function longestSubstring(str, X, Y) { // Length of string var N = str.length; var start = 0; var end = N - 1; var xPos = 0; var yPos = 0; // Find the length of the string // starting with X from the beginning while (true) { if (str[start] === X) { xPos = start; break; } start++; } // Find the length of the string // ending with Y from the end while (true) { if (str[end] === Y) { yPos = end; break; } end--; } // Longest substring var length = yPos - xPos + 1; // Print the length document.write(length); } // Driver code // Given string str var str = "HASFJGHOGAKZZFEGA"; // Starting and Ending characters var X = "A", Y = "Z"; // Function call longestSubstring(str, X, Y); </script> |
Output
12
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
