Given a string S of lowercase alphabets and an integer K, the task is to find whether there exists a substring of length K having only 2 unique characters and the count of both of the characters must be greater than K/3. If such a string exists, print ‘YES‘ else ‘NO‘.
Examples:
Input: “abbad”, K = 4
Output: YES
Explanation: A substring “abba” has 2 a’s and 2 b’s with total length 4, and since, 2 is greater than 4/3, it is a valid substring.Input: “abaaaa”, K = 6
Output: NO
Explanation: No valid substring exists.
Approach: The task can be solved by checking all the K length substrings using the sliding window technique by keeping track of the number of unique characters in the current substring. Follow the below steps to solve the problem:
- Take an unordered map to store the number of characters with their frequency in the current substring, and If
- There are only 2 distinct characters in the current substring, and
- None of the characters has a count less than or equal to K/3
- Current substring is a valid string.
- Hence print YES,
- If no valid substring has been encountered, print NO.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether// a valid substring exists or notvoid checkGoldenString(string S, int k){ // Store the count of distinct chars // with their frequencies unordered_map<char, int> occ; int n = S.length(); // First substring of length k for (int i = 0; i < k; i++) occ[S[i]]++; // Check if it is valid if (occ.size() == 2) { int x = -1, y = -1; for (auto item : occ) { if (x == -1) x = item.second; else y = item.second; } // Count of one of the chars is // greater than k/3 if (x >= k / 3 && y >= k / 3) { cout << "YES\n"; return; } } // Sliding over the entire string for (int i = k; i < n; i++) { // Discarding first character of // previous window occ[S[i - k]]--; // Erase it from the map, if its // frequency becomes 0 if (occ[S[i - k]] == 0) occ.erase(S[i - k]); // Increment count of current char occ[S[i]]++; // Checking valid or not if (occ.size() == 2) { int x = -1, y = -1; for (auto item : occ) { if (x == -1) x = item.second; else y = item.second; } if (x >= k / 3 && y >= k / 3) { cout << "YES\n"; return; } } } // No valid substring is found cout << "NO\n";}// Driver Codeint main(){ int K = 6; string S = "abaaaa"; checkGoldenString(S, K); K = 4; S = "abbaaaa"; checkGoldenString(S, K);} |
Java
// Java program for the above approachimport java.util.HashMap;class GFG { // Function to check whether // a valid substring exists or not public static void checkGoldenString(String S, int k) { // Store the count of distinct chars // with their frequencies HashMap<Character, Integer> occ = new HashMap<Character, Integer>(); int n = S.length(); // First substring of length k for (int i = 0; i < k; i++) { if (occ.containsKey(S.charAt(i))) { occ.put(S.charAt(i), occ.get(S.charAt(i)) + 1); } else { occ.put(S.charAt(i), 1); } } // Check if it is valid if (occ.size() == 2) { int x = -1, y = -1; for (char item : occ.keySet()) { if (x == -1) x = occ.get(item); else y = occ.get(item); } // Count of one of the chars is // greater than k/3 if (x >= k / 3 && y >= k / 3) { System.out.println("YES"); return; } } // Sliding over the entire string for (int i = k; i < n; i++) { // Discarding first character of // previous window occ.put(S.charAt(i - k), occ.get(S.charAt(i - k)) - 1); // Erase it from the map, if its // frequency becomes 0 if (occ.get(S.charAt(i - k)) == 0) occ.remove(S.charAt(i - k)); // Increment count of current char if (occ.containsKey(S.charAt(i))) { occ.put(S.charAt(i), occ.get(S.charAt(i)) + 1); } else { occ.put(S.charAt(i), 1); } // Checking valid or not if (occ.size() == 2) { int x = -1, y = -1; for (char item : occ.keySet()) { if (x == -1) x = occ.get(item); else y = occ.get(item); } if (x >= k / 3 && y >= k / 3) { System.out.println("YES"); return; } } } // No valid substring is found System.out.println("NO"); } // Driver Code public static void main(String args[]) { int K = 6; String S = "abaaaa"; checkGoldenString(S, K); K = 4; S = "abbaaaa"; checkGoldenString(S, K); }}// This code is contributed by saurabh_jaiswal. |
Python3
# Python Program to implement# the above approach# Function to check whether# a valid substring exists or notdef checkGoldenString(S, k): # Store the count of distinct chars # with their frequencies occ = dict() n = len(S) # First substring of length k for i in range(k): if (S[i] not in occ): occ[S[i]] = 1 else: occ[S[i]] += 1 # Check if it is valid if (len(occ) == 2): x = -1 y = -1 for z in occ.values(): if (x == -1): x = z else: y = z # Count of one of the chars is # greater than k/3 if (x >= k // 3 and y >= k // 3): print("YES") return # Sliding over the entire string for i in range(k, n): # Discarding first character of # previous window if (S[i - k] in occ): occ[[S[i - k]]] -= k # Erase it from the map, if its # frequency becomes 0 if (occ[S[i - k]] == 0): del occ[S[i - k]] # Increment count of current char if (S[i] not in occ): occ[S[i]] = 1 else: occ[S[i]] += 1 # Checking valid or not if (len(occ) == 2): x = -1 y = -1 for z in occ.values: if (x == -1): x = z else: y = z if (x >= k // 3 and y >= k // 3): print("YES" + '<br>') return # No valid substring is found print("NO")# Driver CodeK = 6S = "abaaaa"checkGoldenString(S, K)K = 4S = "abbaaaa"checkGoldenString(S, K)# This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to check whether // a valid substring exists or not public static void checkGoldenString(String S, int k) { // Store the count of distinct chars // with their frequencies Dictionary<char, int> occ = new Dictionary<char, int>(); int n = S.Length; // First substring of length k for (int i = 0; i < k; i++) { if (occ.ContainsKey(S[i])) { occ[S[i]] = occ[S[i]] + 1; } else { occ.Add(S[i], 1); } } // Check if it is valid if (occ.Count == 2) { int x = -1, y = -1; foreach (char item in occ.Keys) { if (x == -1) x = occ[item]; else y = occ[item]; } // Count of one of the chars is // greater than k/3 if (x >= k / 3 && y >= k / 3) { Console.WriteLine("YES"); return; } } // Sliding over the entire string for (int i = k; i < n; i++) { // Discarding first character of // previous window occ[S[i - k] ]= occ[S[i - k]] - 1; // Erase it from the map, if its // frequency becomes 0 if (occ[S[i - k]] == 0) occ.Remove(S[i - k]); // Increment count of current char if (occ.ContainsKey(S[i])) { occ[S[i]] = occ[S[i]] + 1; } else { occ.Add(S[i], 1); } // Checking valid or not if (occ.Count == 2) { int x = -1, y = -1; foreach (char item in occ.Keys) { if (x == -1) x = occ[item]; else y = occ[item]; } if (x >= k / 3 && y >= k / 3) { Console.WriteLine("YES"); return; } } } // No valid substring is found Console.WriteLine("NO"); } // Driver Code public static void Main(String []args) { int K = 6; String S = "abaaaa"; checkGoldenString(S, K); K = 4; S = "abbaaaa"; checkGoldenString(S, K); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check whether // a valid substring exists or not function checkGoldenString(S, k) { // Store the count of distinct chars // with their frequencies let occ = new Map(); let n = S.length; // First substring of length k for (let i = 0; i < k; i++) { if (!occ.has(S[i])) { occ.set(S[i], 1); } else { occ.set(S[i], occ.get(S[i]) + 1); } } // Check if it is valid if (occ.size == 2) { let x = -1, y = -1; for (let [key, value] of occ) { if (x == -1) x = value; else y = value; } // Count of one of the chars is // greater than k/3 if (x >= Math.floor(k / 3) && y >= Math.floor(k / 3)) { document.write("YES" + '<br>'); return; } } // Sliding over the entire string for (let i = k; i < n; i++) { // Discarding first character of // previous window if (occ.has(S[i - k])) occ.set([S[i - k]], occ.get(S[i - k]) - 1); // Erase it from the map, if its // frequency becomes 0 if (occ.get(S[i - k]) == 0) occ.delete(S[i - k]); // Increment count of current char if (!occ.has(S[i])) occ.set(S[i], 1); else occ.set(S[i], occ.get(S[i]) + 1) // Checking valid or not if (occ.size == 2) { let x = -1, y = -1; for (let [key, value] of occ) { if (x == -1) x = value; else y = value; } if (x >= Math.floor(k / 3) && y >= Math.floor(k / 3)) { document.write("YES" + '<br>'); return; } } } // No valid substring is found document.write("NO" + '<br>'); } // Driver Code let K = 6; let S = "abaaaa"; checkGoldenString(S, K); K = 4; S = "abbaaaa"; checkGoldenString(S, K); // This code is contributed by Potta Lokesh </script> |
Output
NO YES
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!
Share your thoughts in the comments
