Given a string S and a character K. The task is to find the length of the longest substring of S having all characters the same as character K.
Examples:
Input: S = “abcd1111aabc”, K = ‘1’
Output: 4
Explanation:
1111 is the largest substring of length 4.Input: S = “#1234#@@abcd”, K = ‘@’
Output: 2
Explanation:
@@ is the largest substring of length 2.
Approach: The idea is to iterate over the string and check the following two conditions:
- If the current character is the same as character K then increase the value of the counter by one.
- If the current character is not the same as K then update the previous count and reinitialize the counter to 0.
- Repeat the steps above till the length of the string.
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 length of// longest sub-string having all// characters same as character Kint length_substring(string S, char K){ // Initialize variables int curr_cnt = 0, prev_cnt = 0, max_len; // Iterate till size of string for (int i = 0; i < S.size(); i++) { // Check if current character is K if (S[i] == K) { curr_cnt += 1; } else { prev_cnt = max(prev_cnt, curr_cnt); curr_cnt = 0; } } prev_cnt = max(prev_cnt, curr_cnt); // Assigning the max // value to max_len max_len = prev_cnt; return max_len;}// Driver codeint main(){ string S = "abcd1111aabc"; char K = '1'; // Function call cout << length_substring(S, K); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG {// Function to find the length of// longest sub-string having all// characters same as character Kstatic int length_substring(String S, char K){ // Initialize variables int curr_cnt = 0, prev_cnt = 0, max_len; // Iterate till size of string for (int i = 0; i < S.length(); i++) { // Check if current character is K if (S.charAt(i) == K) { curr_cnt += 1; } else { prev_cnt = Math.max(prev_cnt, curr_cnt); curr_cnt = 0; } } prev_cnt = Math.max(prev_cnt, curr_cnt); // Assigning the max // value to max_len max_len = prev_cnt; return max_len;}// Driver codepublic static void main(String[] args){ String S = "abcd1111aabc"; char K = '1'; // Function call System.out.print(length_substring(S, K));}}// This code is contributed by Chitranayal |
Python3
# Python3 program for the above approach# Function to find the length of# longest sub-string having all# characters same as character Kdef length_substring(S, K): # Initialize variables curr_cnt = 0 prev_cnt = 0 max_len = 0 # Iterate till size of string for i in range(len(S)): # Check if current character is K if (S[i] == K): curr_cnt += 1 else: prev_cnt = max(prev_cnt, curr_cnt) curr_cnt = 0 prev_cnt = max(prev_cnt, curr_cnt) # Assigning the max # value to max_len max_len = prev_cnt return max_len# Driver codeif __name__ == '__main__': S = "abcd1111aabc" K = '1' # Function call print(length_substring(S, K))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the length of// longest sub-string having all// characters same as character Kstatic int length_substring(string S, char K){ // Initialize variables int curr_cnt = 0, prev_cnt = 0, max_len; // Iterate till size of string for(int i = 0; i < S.Length; i++) { // Check if current character is K if (S[i] == K) { curr_cnt += 1; } else { prev_cnt = Math.Max(prev_cnt, curr_cnt); curr_cnt = 0; } } prev_cnt = Math.Max(prev_cnt, curr_cnt); // Assigning the max // value to max_len max_len = prev_cnt; return max_len;}// Driver codestatic public void Main(){ string S = "abcd1111aabc"; char K = '1'; // Function call Console.WriteLine(length_substring(S, K));}}// This code is contributed by rag2127 |
Javascript
<script>// Javascript program for// the above approach// Function to find the length of// longest sub-string having all// characters same as character Kfunction length_substring(S, K){ // Initialize variables let curr_cnt = 0, prev_cnt = 0, max_len; // Iterate till size of string for(let i = 0; i < S.length; i++) { // Check if current character is K if (S[i] == K) { curr_cnt += 1; } else { prev_cnt = Math.max(prev_cnt, curr_cnt); curr_cnt = 0; } } prev_cnt = Math.max(prev_cnt, curr_cnt); // Assigning the max // value to max_len max_len = prev_cnt; return max_len;}// Driver codelet S = "abcd1111aabc";let K = '1';// Function calldocument.write(length_substring(S, K));// This code is contributed by avanitrachhadiya2155</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Another approach to solve above problem :-
- Define a function length_substring(S, K) that takes a string S and a character K as input.
- In the function, initialize left, right, max_len, count, and freq. left and right are pointers that point to the leftmost and rightmost indices of the current substring being considered. max_len is the length of the longest substring found so far. count is the number of characters in the current substring that are not equal to K. freq is a list of 26 elements that stores the frequency of each character in the current substring.
- While right is less than the length of S, increment the frequency of the character at S[right] in freq. If S[right] is not equal to K, increment count.
- While count is greater than 0, decrement the frequency of the character at S[left] in freq. If S[left] is not equal to K, decrement count and increment left.
- Update max_len to be the maximum of max_len and right-left+1.
- Increment right and repeat steps 3-5 until right is equal to the length of S.
- Return max_len.
Here is the implementation of above approach:-
C++
#include <iostream>#include <string>using namespace std;int length_substring(string S, char K) { int left = 0, right = 0; int max_len = 0, count = 0; int freq[26] = {0}; while (right < S.length()) { freq[S[right]-'a'] += 1; if (S[right] != K) { count += 1; } while (count > 0) { freq[S[left]-'a'] -= 1; if (S[left] != K) { count -= 1; } left += 1; } max_len = max(max_len, right-left+1); right += 1; } return max_len;}int main() { string S = "abcd1111aabc"; char K = '1'; cout << length_substring(S, K) << endl; return 0;} |
Java
import java.util.*;public class Main { public static int length_substring(String S, char K) { int left = 0, right = 0; int max_len = 0, count = 0; int[] freq = new int[26]; while (right < S.length()) { char c = S.charAt(right); if (c >= 'a' && c <= 'z') { freq[c-'a'] += 1; if (c != K) { count += 1; } } while (count > 0) { char d = S.charAt(left); if (d >= 'a' && d <= 'z') { freq[d-'a'] -= 1; if (d != K) { count -= 1; } } left += 1; } max_len = Math.max(max_len, right-left+1); right += 1; } return max_len; } public static void main(String[] args) { String S = "abcd1111aabc"; char K = '1'; System.out.println(length_substring(S, K)); }} |
Python3
import redef length_substring(S, K): pattern = r'[' + K + r']+' substrings = re.findall(pattern, S) if not substrings: return 0 return max(map(len, substrings))if __name__ == '__main__': S = "abcd1111aabc" K = '1' print(length_substring(S, K)) |
C#
using System;public class MainClass { public static int length_substring(string S, char K) { int left = 0, right = 0; int max_len = 0, count = 0; int[] freq = new int[256]; // initialize array with a larger size while (right < S.Length) { freq[S[right]] += 1; if (S[right] != K) { count += 1; } while (count > 0) { freq[S[left]] -= 1; if (S[left] != K) { count -= 1; } left += 1; } max_len = Math.Max(max_len, right-left+1); right += 1; } return max_len; } public static void Main(string[] args) { string S = "abcd1111aabc"; char K = '1'; Console.WriteLine(length_substring(S, K)); }} |
Javascript
function lengthSubstring(S, K) { let left = 0; let right = 0; let maxLen = 0; let count = 0; let freq = new Array(26).fill(0); while (right < S.length) { freq[S.charCodeAt(right) - 'a'.charCodeAt(0)] += 1; if (S[right] != K) { count += 1; } while (count > 0) { freq[S.charCodeAt(left) - 'a'.charCodeAt(0)] -= 1; if (S[left] != K) { count -= 1; } left += 1; } maxLen = Math.max(maxLen, right - left + 1); right += 1; } return maxLen;}const S = "abcd1111aabc";const K = '1';console.log(lengthSubstring(S, K)); |
Output
4
Time complexity:
- The while loop runs for each character in the string, so it has a time complexity of O(n).
- The inner while loop also runs at most n times, so it has a time complexity of O(n) as well.
- The operations inside the loops are all constant time operations, so they don’t affect the time complexity.
- Therefore, the overall time complexity of the algorithm is O(n).
Space Complexity:
- The algorithm uses a frequency array of size 26, which is constant space.
- Therefore, the space complexity of the algorithm is 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!
