Given a string S consisting of lowercase English alphabets, the task is to find the length of the longest subsequence from the given string such that the difference between the largest and smallest ASCII value is exactly 1.
Examples:
Input: S = “acbbebcg”
Output: 5
Explanation: The longest subsequence of required type is “cbbbc”, whose length is 5.
The difference between largest (‘c’) and smallest (‘b’) ASCII values is c – b = 99 – 98 = 1, which is minimum possible.Input: S = “abcd”
Output: 2
Explanation: The longest subsequence of the required type is “ab”, whose length is 2. Other possible subsequences are “bc” and “cd”.
The difference between largest(‘b’) and smallest(‘a’) ASCII values is b – a = 98 – 97 = 1.
Naive Approach: The simplest approach to solve the problem is to generate all possible subsequences of the given string S and print the length of the subsequence which is of maximum length and having a difference between ASCII values of the largest and smallest character is exactly equal to 1.
Time Complexity: O(N * 2N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the main idea is to use a Map to optimize the above approach. Follow the steps below to solve the problem:
- Initialize a variable, say maxLength, that stores the maximum length of the resultant subsequence.
- Store the frequency of characters in a Map, say M.
- Traverse the string and for each character, say ch, check if there exists character c with ASCII value (ch – 1) in the map M or not. If found to be true, then update maxLength as the maximum of maxLength and (M[ch] + M[ch – 1]).
- After completing the above steps, print the value of maxLength as the result.
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 maximum length of// subsequence having difference of ASCII// value of longest and smallest character as 1int maximumLengthSubsequence(string str){ // Stores frequency of characters unordered_map<char, int> mp; // Iterate over characters // of the string for (char ch : str) { mp[ch]++; } // Stores the resultant // length of subsequence int ans = 0; for (char ch : str) { // Check if there exists any // elements with ASCII value // one less than character ch if (mp.count(ch - 1)) { // Size of current subsequence int curr_max = mp[ch] + mp[ch - 1]; // Update the value of ans ans = max(ans, curr_max); } } // Print the resultant count cout << ans;}// Driver Codeint main(){ string S = "acbbebcg"; maximumLengthSubsequence(S); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum length of// subsequence having difference of ASCII// value of longest and smallest character as 1static void maximumLengthSubsequence(String str){ // Stores frequency of characters HashMap<Character, Integer> mp = new HashMap<>(); for(char ch : str.toCharArray()) { mp.put(ch, mp.getOrDefault(ch, 0) + 1); } // Stores the resultant // length of subsequence int ans = 0; for(char ch : str.toCharArray()) { // Check if there exists any // elements with ASCII value // one less than character ch if (mp.containsKey((char)(ch - 1))) { // Size of current subsequence int curr_max = mp.get(ch) + mp.get((char)(ch - 1)); // Update the value of ans ans = Math.max(ans, curr_max); } } // Print the resultant count System.out.println(ans);}// Driver Codepublic static void main(String[] args){ String S = "acbbebcg"; maximumLengthSubsequence(S);}}// This code is contributed by aadityapburujwale |
Python3
# Python3 program for the above approach# Function to find the maximum length of# subsequence having difference of ASCII# value of longest and smallest character as 1def maximumLengthSubsequence(str): # Stores frequency of characters mp = {} # Iterate over characters # of the string for ch in str: if ch in mp.keys(): mp[ch] += 1 else: mp[ch] = 1 # Stores the resultant # length of subsequence ans = 0 for ch in str: # Check if there exists any # elements with ASCII value # one less than character ch if chr(ord(ch) - 1) in mp.keys(): # Size of current subsequence curr_max = mp[ch] if chr(ord(ch) - 1) in mp.keys(): curr_max += mp[chr(ord(ch) - 1)] # Update the value of ans ans = max(ans, curr_max) # Print the resultant count print(ans)# Driver CodeS = "acbbebcg"maximumLengthSubsequence(S)# This code is contributed by Stream_Cipher |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Function to find the maximum length of// subsequence having difference of ASCII// value of longest and smallest character as 1static void maximumLengthSubsequence(String str){ // Stores frequency of characters Dictionary<char, int> mp = new Dictionary<char, int>(); foreach(char ch in str.ToCharArray()) { if(mp.ContainsKey(ch)) mp[ch] = mp[ch] + 1; else mp.Add(ch, 1); } // Stores the resultant // length of subsequence int ans = 0; foreach(char ch in str.ToCharArray()) { // Check if there exists any // elements with ASCII value // one less than character ch if (mp.ContainsKey((char)(ch - 1))) { // Size of current subsequence int curr_max = mp[ch] + mp[(char)(ch - 1)]; // Update the value of ans ans = Math.Max(ans, curr_max); } } // Print the resultant count Console.WriteLine(ans);}// Driver Codepublic static void Main(String[] args){ String S = "acbbebcg"; maximumLengthSubsequence(S);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum length of // subsequence having difference of ASCII // value of longest and smallest character as 1 function maximumLengthSubsequence(str) { // Stores frequency of characters var mp = {}; var temp = str.split(""); for (const ch of temp) { if (mp.hasOwnProperty(ch)) mp[ch] = mp[ch] + 1; else mp[ch] = 1; } // Stores the resultant // length of subsequence var ans = 0; for (const ch of temp) { // Check if there exists any // elements with ASCII value // one less than character ch if (mp.hasOwnProperty(String.fromCharCode(ch.charCodeAt(0) - 1))) { // Size of current subsequence var curr_max = mp[ch] + mp[String.fromCharCode(ch.charCodeAt(0) - 1)]; // Update the value of ans ans = Math.max(ans, curr_max); } } // Print the resultant count document.write(ans); } // Driver Code var S = "acbbebcg"; maximumLengthSubsequence(S); // This code is contributed by rdtank. </script> |
Output:
5
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!
