Given a string of lowercase characters S, the task is to find longest subsequence of the string with no 3 consecutive identical characters.
Examples:
Input: S = “eedaaad”
Output: eedaad
Explanation: One occurrence of letter a is deleted.Input: xxxtxxx
Output: xxtxx
Approach: The task can be solved by checking every window of size 3. If any of the 3 characters mismatch, append it to the resultant string, else continue. At last, print the resultant string.
Effective Approach:
1. Define a static method named “filterString” that takes a string “s1” as input and returns a string.
2. Create a StringBuilder object “sb1” to store the filtered string.
3. Append the first two characters of “s1” to “sb1”.
4. Loop over the remaining characters of “s1” starting from the third character:
a. Check if the current character is different from the previous two characters.
b. If it is, append the current character to “sb1”.
5. Return the filtered string by calling the “toString” method on “sb1”.
6. In the main method:
a. Create a string “s” and assign it a value.
b. Call the “filterString” method with “s” as input and assign the result to “res”.
c. Print the value of “res”.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the// longest subsequencestring filterString(string s1){ string sb1 = ""; // Append the first character sb1 += s1[0]; // Append the second character sb1 += (s1[1]); // Loop for i=2 to n for (int i = 2; i < s1.length(); ++i) { // If consecutive three element // are not equal then append if (s1[i] != s1[i - 1] || s1[i] != s1[i - 2]) { sb1 += s1[i]; } } return sb1;}// Driver Codeint main(){ string s = "eedaaad"; string res = filterString(s); cout << (res); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java program for the above approachclass Solution { // Function to find the // longest subsequence public static String filterString(String s1) { StringBuilder sb1 = new StringBuilder(); // Append the first character sb1.append(s1.charAt(0)); // Append the second character sb1.append(s1.charAt(1)); // Loop for i=2 to n for (int i = 2; i < s1.length(); ++i) { // If consecutive three element // are not equal then append if (s1.charAt(i) != s1.charAt(i - 1) || s1.charAt(i) != s1.charAt(i - 2)) { sb1.append(s1.charAt(i)); } } return sb1.toString(); } // Driver Code public static void main(String[] args) { String s = "eedaaad"; String res = filterString(s); System.out.println(res); }} |
Python3
# Python 3 code for the above approach# Function to find the# longest subsequencedef filterString(s1): sb1 = "" # Append the first character sb1 += s1[0] # Append the second character sb1 += (s1[1]) # Loop for i=2 to n for i in range(2, len(s1)): # If consecutive three element # are not equal then append if (s1[i] != s1[i - 1] or s1[i] != s1[i - 2]): sb1 += s1[i] return sb1# Driver Codeif __name__ == "__main__": s = "eedaaad" res = filterString(s) print(res) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Text;class Solution{ // Function to find the // longest subsequence public static string filterstring(string s1) { StringBuilder sb1 = new StringBuilder(); // Append the first character sb1.Append(s1[0]); // Append the second character sb1.Append(s1[1]); // Loop for i=2 to n for (int i = 2; i < s1.Length; ++i) { // If consecutive three element // are not equal then append if (s1[i] != s1[i - 1] || s1[i] != s1[i - 2]) { sb1.Append(s1[i]); } } return sb1.ToString(); } // Driver Code public static void Main() { string s = "eedaaad"; string res = filterstring(s); Console.Write(res); }}// This code is contributed by gfgking. |
Javascript
<script> // JavaScript code for the above approach // Function to find the // longest subsequence const filterString = (s1) => { let sb1 = ""; // Append the first character sb1 += s1[0]; // Append the second character sb1 += (s1[1]); // Loop for i=2 to n for (let i = 2; i < s1.length; ++i) { // If consecutive three element // are not equal then append if (s1[i] != s1[i - 1] || s1[i] != s1[i - 2]) { sb1 += s1[i]; } } return sb1; } // Driver Code let s = "eedaaad"; let res = filterString(s); document.write(res); // This code is contributed by rakeshsahni</script> |
eedaad
Time Complexity: O(N), where N is the length of string
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
