Given a string S consisting of lowercase English alphabets, the task is to find the longest substring from the given string such that no two adjacent characters are neighbouring English alphabets.
Examples:
Input: S = “aabdml”
Output: “bdm”
Explanation: Substring “bdm” is the longest substring which satisfies the given condition.Input: S = “abc”
Output: “a”
Explanation: Substrings “a”, “b”, “c” satisfies the given condition. Print any one of them.
Approach: Follow the steps below to solve the problem:
- Initialize an empty string, say T, to store all the temporary substrings during iteration.
- Initialize another string, say ans, to store the longest substring as per the given conditions and a variable, say len, to store the length of the longest substring.
- Append the first character of the string to ans.
- Traverse the string in the range of indices [1, S.length()] and perform the following operations:
- If the absolute difference between ASCII values of the adjacent characters is 1, then update ans and the length of the longest string and set T equal to the current character for the next iteration.
- Otherwise, append the current character to string T.
- Check again for the longest substring and update the values accordingly.
- Print the longest substring obtained in variable ans.
Below is the implementation of the above approach:
C++
// C++ program for// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the longest substring// satisfying the given conditionvoid findSubstring(string S){ // Stores all temporary substrings string T = ""; // Stores the longest substring string ans = ""; // Stores the length // of the substring T int l = 0; // Stores the first // character of string S T += S[0]; // Traverse the string for (int i = 1; i < S.length(); i++) { // If the absolute difference is 1 if (abs(S[i] - S[i - 1]) == 1) { // Update the length of // substring T l = T.length(); // Update the longest substring if (l > ans.length()) { ans = T; } T = ""; T += S[i]; } // Otherwise, stores the current // character else { T += S[i]; } } // Again checking for // longest substring // and update accordingly l = (int)T.length(); if (l > (int)ans.length()) { ans = T; } // Print the longest substring cout << ans << endl;}// Driver Codeint main(){ // Given string string S = "aabdml"; // Function call to find // the longest substring // satisfying given condition findSubstring(S); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the longest substring // satisfying the given condition static void findSubstring(String S) { // Stores all temporary substrings String T = ""; // Stores the longest substring String ans = ""; // Stores the length // of the substring T int l = 0; // Stores the first // character of string S T += S.charAt(0); // Traverse the string for (int i = 1; i < S.length(); i++) { // If the absolute difference is 1 if (Math.abs(S.charAt(i) - S.charAt(i - 1)) == 1) { // Update the length of // substring T l = T.length(); // Update the longest substring if (l > ans.length()) { ans = T; } T = ""; T += S.charAt(i); } // Otherwise, stores the current // character else { T += S.charAt(i); } } // Again checking for // longest substring // and update accordingly l = T.length(); if (l > ans.length()) { ans = T; } // Print the longest substring System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given string String S = "aabdml"; // Function call to find // the longest substring // satisfying given condition findSubstring(S); }}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for# the above approach# Function to find the longest substring# satisfying the given conditiondef findSubstring(S): # Stores all temporary substrings T = "" # Stores the longest substring ans = "" # Stores the length # of the subT l = 0 # Stores the first # character of S T += S[0] # Traverse the string for i in range(1,len(S)): # If the absolute difference is 1 if (abs(ord(S[i]) - ord(S[i - 1])) == 1): # Update the length of # subT l = len(T) # Update the longest substring if (l > len(ans)): ans = T T = "" T += S[i] # Otherwise, stores the current # character else: T += S[i] # Again checking for # longest substring # and update accordingly l = len(T) if (l > len(ans)): ans = T # Print the longest substring print (ans)# Driver Codeif __name__ == '__main__': # Given string S = "aabdml" # Function call to find # the longest substring # satisfying given condition findSubstring(S) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the longest substring// satisfying the given conditionstatic void findSubstring(string S){ // Stores all temporary substrings string T = ""; // Stores the longest substring string ans = ""; // Stores the length // of the substring T int l = 0; // Stores the first // character of string S T += S[0]; // Traverse the string for (int i = 1; i < S.Length; i++) { // If the absolute difference is 1 if (Math.Abs(S[i] - S[i - 1]) == 1) { // Update the length of // substring T l = T.Length; // Update the longest substring if (l > ans.Length) { ans = T; } T = ""; T += S[i]; } // Otherwise, stores the current // character else { T += S[i]; } } // Again checking for // longest substring // and update accordingly l = T.Length; if (l > ans.Length) { ans = T; } // Print the longest substring Console.Write(ans);}// Driver Codepublic static void Main(String[] args){ // Given string string S = "aabdml"; // Function call to find // the longest substring // satisfying given condition findSubstring(S);}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for the above approach // Function to find the longest substring // satisfying the given condition function findSubstring(S) { // Stores all temporary substrings var T = ""; // Stores the longest substring var ans = ""; // Stores the length // of the substring T var l = 0; // Stores the first // character of string S T += S[0]; // Traverse the string for (var i = 1; i < S.length; i++) { // If the absolute difference is 1 if (Math.abs(S[i].charCodeAt(0) - S[i - 1].charCodeAt(0)) === 1) { // Update the length of // substring T l = T.length; // Update the longest substring if (l > ans.length) { ans = T; } T = ""; T += S[i]; } // Otherwise, stores the current // character else { T += S[i]; } } // Again checking for // longest substring // and update accordingly l = T.length; if (l > ans.length) { ans = T; } // Print the longest substring document.write(ans); } // Driver Code // Given string var S = "aabdml"; // Function call to find // the longest substring // satisfying given condition findSubstring(S); </script> |
Output:
bdm
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
