Given a string s of length n consisting only of uppercase English letters ('A'–'Z') and an integer k (0 < k < n), you can change at most k characters in the string. find the length of the longest substring that can be made of the same character after performing at most k changes.
Input : k = 2, s = ABABA
Output : 5
We can get maximum length by replacing 2 B's with A'sInput : k = 4, s = HHHHHH
Output : 6
We get maximum length 6 without any replacement
Try it on GfG Practice
Table of Content
Naive Solution - O(n^3) Time
- Consider all substrings by choosing start l and end r.
- For each substring, find the most frequent character using getMaxFreq.
- If (substring length − max frequency) ≤ k, update the maximum length.
#include <iostream>
#include <unordered_map>
using namespace std;
int getMaxFreq(string &s, int l, int r) {
unordered_map<char, int> m;
int res = 1;
// Count the frequency of each character
// in the substring
for (int i = l; i <= r; ++i)
m[s[i]]++;
// Find the maximum frequency of any character
for (auto &e : m)
res = max(res, e.second);
return res;
}
// function to find the maximum length of substring
// with at most k changes
int longestSubstr(string& s, int k)
{
int maxlen = 1;
int n = s.size();
// Try every possible starting point of the substring
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
// Get the maximum frequency of any
// character in the substring [l, r]
int f = getMaxFreq(s, l, r);
// If the number of changes required is <= k,
// update the maximum length
if (r - l + 1 - f <= k)
maxlen = max(maxlen, r - l + 1);
}
}
return maxlen;
}
int main()
{
int k = 2;
string s = "ABABA";
cout << "Maximum length = " << longestSubstr(s, k) << endl;
k = 4;
string B = "HHHHHH";
cout << "Maximum length = " << longestSubstr(B, k) << endl;
return 0;
}
#include <stdio.h>
#include <string.h>
int getMaxFreq(char s[], int l, int r) {
int m[256] = {0};
int res = 1;
// Count the frequency of each character
// in the substring
for (int i = l; i <= r; ++i)
m[s[i]]++;
// Find the maximum frequency of any character
for (int i = 0; i < 256; ++i)
if (m[i] > res)
res = m[i];
return res;
}
// Function to find the maximum length of substring
// with at most k changes
int longestSubstr(char s[], int k)
{
int maxlen = 1;
int n = strlen(s);
// Try every possible starting point of the substring
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
// Get the maximum frequency of any
// character in the substring [l, r]
int f = getMaxFreq(s, l, r);
// If the number of changes required is <= k,
// update the maximum length
if (r - l + 1 - f <= k)
maxlen = (r - l + 1 > maxlen) ? r - l + 1 : maxlen;
}
}
return maxlen;
}
int main() {
int k = 2;
char s[] = "ABABA";
printf("Maximum length = %d\n", longestSubstr(s, k));
k = 4;
char B[] = "HHHHHH";
printf("Maximum length = %d\n", longestSubstr(B, k));
return 0;
}
import java.util.HashMap;
class GfG {
static int getMaxFreq(String s, int l, int r) {
HashMap<Character, Integer> m = new HashMap<>();
int res = 1;
// Count the frequency of each character
// in the substring
for (int i = l; i <= r; ++i)
m.put(s.charAt(i), m.getOrDefault(s.charAt(i), 0) + 1);
// Find the maximum frequency of any character
for (int value : m.values())
res = Math.max(res, value);
return res;
}
// Function to find the maximum length of substring
// with at most k changes
static int longestSubstr(String s, int k) {
int maxlen = 1;
int n = s.length();
// Try every possible starting point of the substring
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
// Get the maximum frequency of any
// character in the substring [l, r]
int f = getMaxFreq(s, l, r);
// If the number of changes required is <= k,
// update the maximum length
if (r - l + 1 - f <= k)
maxlen = Math.max(maxlen, r - l + 1);
}
}
return maxlen;
}
public static void main(String[] args) {
int k = 2;
String s = "ABABA";
System.out.println("Maximum length = " + longestSubstr(s, k));
k = 4;
String B = "HHHHHH";
System.out.println("Maximum length = " + longestSubstr(B, k));
}
}
def getMaxFreq(s, l, r):
m = {}
res = 1
# Count the frequency of each character
# in the substring
for i in range(l, r + 1):
m[s[i]] = m.get(s[i], 0) + 1
# Find the maximum frequency of any character
res = max(m.values())
return res
# Function to find the maximum length of substring
# with at most k changes
def longestSubstr(s, k):
maxlen = 1
n = len(s)
# Try every possible starting point of the substring
for l in range(n):
for r in range(l, n):
# Get the maximum frequency of any
# character in the substring [l, r]
f = getMaxFreq(s, l, r)
# If the number of changes required is <= k,
# update the maximum length
if r - l + 1 - f <= k:
maxlen = max(maxlen, r - l + 1)
return maxlen
if __name__ == "__main__":
k = 2
s = "ABABA"
print("Maximum length =", longestSubstr(s, k))
k = 4
B = "HHHHHH"
print("Maximum length =", longestSubstr(B, k))
using System;
using System.Collections.Generic;
class GfG {
static int GetMaxFreq(string s, int l, int r) {
Dictionary<char, int> m = new Dictionary<char, int>();
int res = 1;
// Count the frequency of each character
// in the substring
for (int i = l; i <= r; ++i) {
if (!m.ContainsKey(s[i]))
m[s[i]] = 0;
m[s[i]]++;
}
// Find the maximum frequency of any character
foreach (var entry in m) {
res = Math.Max(res, entry.Value);
}
return res;
}
// Function to find the maximum length of substring
// with at most k changes
static int LongestSubstr(string s, int k) {
int maxlen = 1;
int n = s.Length;
// Try every possible starting point of the substring
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
// Get the maximum frequency of any
// character in the substring [l, r]
int f = GetMaxFreq(s, l, r);
// If the number of changes required is <= k,
// update the maximum length
if (r - l + 1 - f <= k)
maxlen = Math.Max(maxlen, r - l + 1);
}
}
return maxlen;
}
static void Main() {
int k = 2;
string s = "ABABA";
Console.WriteLine("Maximum length = " + LongestSubstr(s, k));
k = 4;
string B = "HHHHHH";
Console.WriteLine("Maximum length = " + LongestSubstr(B, k));
}
}
function getMaxFreq(s, l, r) {
const m = {};
let res = 1;
// Count the frequency of each character
// in the substring
for (let i = l; i <= r; ++i) {
m[s[i]] = (m[s[i]] || 0) + 1;
}
// Find the maximum frequency of any character
res = Math.max(...Object.values(m));
return res;
}
// Function to find the maximum length of substring
// with at most k changes
function longestSubstr(s, k) {
let maxlen = 1;
const n = s.length;
// Try every possible starting point of the substring
for (let l = 0; l < n; ++l) {
for (let r = l; r < n; ++r) {
// Get the maximum frequency of any
// character in the substring [l, r]
const f = getMaxFreq(s, l, r);
// If the number of changes required is <= k,
// update the maximum length
if (r - l + 1 - f <= k)
maxlen = Math.max(maxlen, r - l + 1);
}
}
return maxlen;
}
// Driver code
let k = 2;
let s = "ABABA";
console.log("Maximum length =", longestSubstr(s, k));
k = 4;
let B = "HHHHHH";
console.log("Maximum length =", longestSubstr(B, k));
Output
Maximum length = 5 Maximum length = 6
Expected Approach 1 - Window Sliding for Every Character - O(26 * n) Time
- Check each character from 'A' to 'Z' and treat it as the target character for the substring.
- Use a sliding window to find the longest substring that can be converted to that character with at most k changes.
- If the number of different characters exceeds k, shrink the window from the left.
- Track the maximum substring length among all characters and return it.
#include <iostream>
using namespace std;
int longestSubstr(string &s, int k)
{
int res = 0, n = s.size();
// Try replacing other characters to form
// a string of each character 'A' to 'Z'
for (char c = 'A'; c <= 'Z'; c++)
{
int l = 0, r = 0, cnt = 0;
// Sliding window from l to r
while (r < n)
{
if (s[r] == c)
r++;
else if (cnt < k)
r++, cnt++;
else if (s[l] == c)
l++;
else
l++, cnt--;
// Update the maximum length of substring
res = max(res, r - l);
}
}
return res;
}
int main()
{
int k = 2;
string s = "ABABA";
cout << "Maximum length = " << longestSubstr(s, k) << endl;
k = 4;
string B = "HHHHHH";
cout << "Maximum length = " << longestSubstr(B, k) << endl;
return 0;
}
#include <stdio.h>
#include <string.h>
int longestSubstr(char *s, int k) {
int res = 0;
int n = strlen(s);
// Try replacing other characters to form
// a string of each character 'A' to 'Z'
for (char c = 'A'; c <= 'Z'; c++) {
int l = 0, r = 0, cnt = 0;
// Sliding window from l to r
while (r < n) {
if (s[r] == c)
r++;
else if (cnt < k)
r++, cnt++;
else if (s[l] == c)
l++;
else
l++, cnt--;
// Update the maximum length of substring
if (r - l > res)
res = r - l;
}
}
return res;
}
int main() {
int k = 2;
char s[] = "ABABA";
printf("Maximum length = %d\n", longestSubstr(s, k));
k = 4;
char B[] = "HHHHHH";
printf("Maximum length = %d\n", longestSubstr(B, k));
return 0;
}
import java.util.*;
class GfG {
static int longestSubstr(String s, int k) {
int res = 0, n = s.length();
// Try replacing other characters to form
// a string of each character 'A' to 'Z'
for (char c = 'A'; c <= 'Z'; c++) {
int l = 0, r = 0, cnt = 0;
// Sliding window from l to r
while (r < n) {
if (s.charAt(r) == c) {
r++;
} else if (cnt < k) {
r++;
cnt++;
} else if (s.charAt(l) == c) {
l++;
} else {
l++;
cnt--;
}
// Update the maximum length of substring
res = Math.max(res, r - l);
}
}
return res;
}
public static void main(String[] args) {
int k = 2;
String s = "ABABA";
System.out.println("Maximum length = " + longestSubstr(s, k));
k = 4;
String B = "HHHHHH";
System.out.println("Maximum length = " + longestSubstr(B, k));
}
}
def longest_substr(s, k):
res = 0
n = len(s)
# Try replacing other characters to form
# a string of each character 'A' to 'Z'
for c in range(ord('A'), ord('Z') + 1):
l, r, cnt = 0, 0, 0
# Sliding window from l to r
while r < n:
if s[r] == chr(c):
r += 1
elif cnt < k:
r += 1
cnt += 1
elif s[l] == chr(c):
l += 1
else:
l += 1
cnt -= 1
# Update the maximum length of substring
res = max(res, r - l)
return res
if __name__ == "__main__":
k = 2
s = "ABABA"
print("Maximum length =", longest_substr(s, k))
k = 4
B = "HHHHHH"
print("Maximum length =", longest_substr(B, k))
using System;
class GfG {
static int LongestSubstr(string s, int k) {
int res = 0, n = s.Length;
// Try replacing other characters to form
// a string of each character 'A' to 'Z'
for (char c = 'A'; c <= 'Z'; c++) {
int l = 0, r = 0, cnt = 0;
// Sliding window from l to r
while (r < n) {
if (s[r] == c) {
r++;
}
else if (cnt < k) {
r++;
cnt++;
}
else if (s[l] == c) {
l++;
}
else {
l++;
cnt--;
}
// Update the maximum length of substring
res = Math.Max(res, r - l);
}
}
return res;
}
static void Main(string[] args) {
int k = 2;
string s = "ABABA";
Console.WriteLine("Maximum length = " + LongestSubstr(s, k));
k = 4;
string B = "HHHHHH";
Console.WriteLine("Maximum length = " + LongestSubstr(B, k));
}
}
function longestSubstr(s, k) {
let res = 0;
let n = s.length;
// Try replacing other characters to form
// a string of each character 'A' to 'Z'
for (let c = 'A'.charCodeAt(0); c <= 'Z'.charCodeAt(0); c++) {
let l = 0, r = 0, cnt = 0;
// Sliding window from l to r
while (r < n) {
if (s[r] === String.fromCharCode(c))
r++;
else if (cnt < k)
r++, cnt++;
else if (s[l] === String.fromCharCode(c))
l++;
else
l++, cnt--;
// Update the maximum length of substring
res = Math.max(res, r - l);
}
}
return res;
}
// Driver code
function main() {
let k = 2;
let s = "ABABA";
console.log("Maximum length = " + longestSubstr(s, k));
k = 4;
let B = "HHHHHH";
console.log("Maximum length = " + longestSubstr(B, k));
}
main();
Output
Maximum length = 5 Maximum length = 6
Expected Approach 2 - Window Sliding with Hash Map - O(n) Time
- Maintain a sliding window (l, r) and store character frequencies using a hash map.
- Track the most frequent character (maxFreq) in the window.
- If (window size − maxFreq) > k, shrink the window; otherwise expand it and update the maximum length.
#include <iostream>
#include <unordered_map>
using namespace std;
int longestSubstr(string& s, int k) {
int n = s.size();
unordered_map<char, int> freq;
int maxFreq = 0;
int res = 0;
int l = 0; // Left boundary of the window
// Right boundary of the window
for (int r = 0; r < n; ++r) {
// Increase the frequency of the
// current character
freq[s[r]]++;
// Update maxFreq with the frequency of
// the most frequent character in the
// current window
maxFreq = max(maxFreq, freq[s[r]]);
// Shrink the window if more than k changes
// required
if (r - l + 1 - maxFreq > k) {
freq[s[l]]--;
++l;
}
// Update the maximum length of the substring
res = max(res, r - l + 1);
}
return res;
}
int main() {
int k = 2;
string s = "ABABA";
cout << "Maximum length = " << longestSubstr(s, k) << endl;
k = 4;
s = "HHHHHH";
cout << "Maximum length = " << longestSubstr(s, k) << endl;
return 0;
}
#include <stdio.h>
#include <string.h>
int longestSubstr(char *s, int k) {
int n = strlen(s);
int freq[256] = {0}; // Initialize character frequency array
int maxFreq = 0;
int res = 0;
int l = 0; // Left boundary of the window
// Right boundary of the window
for (int r = 0; r < n; ++r) {
// Increase the frequency of the
// current character
freq[(unsigned char)s[r]]++;
// Update maxFreq with the frequency of
// the most frequent character in the
// current window
if (freq[(unsigned char)s[r]] > maxFreq)
maxFreq = freq[(unsigned char)s[r]];
// Shrink the window if more than k changes
// required
if (r - l + 1 - maxFreq > k) {
freq[(unsigned char)s[l]]--;
++l;
}
// Update the maximum length of the substring
if (r - l + 1 > res)
res = r - l + 1;
}
return res;
}
int main() {
int k = 2;
char s[] = "ABABA";
printf("Maximum length = %d\n", longestSubstr(s, k));
k = 4;
char B[] = "HHHHHH";
printf("Maximum length = %d\n", longestSubstr(B, k));
return 0;
}
import java.util.HashMap;
class GfG {
static int longestSubstr(String s, int k) {
int n = s.length();
HashMap<Character, Integer> freq = new HashMap<>();
int maxFreq = 0;
int res = 0;
int l = 0; // Left boundary of the window
// Right boundary of the window
for (int r = 0; r < n; ++r) {
// Increase the frequency of the
// current character
freq.put(s.charAt(r), freq.getOrDefault(s.charAt(r), 0) + 1);
// Update maxFreq with the frequency of
// the most frequent character in the
// current window
maxFreq = Math.max(maxFreq, freq.get(s.charAt(r)));
// Shrink the window if more than k changes
// required
if (r - l + 1 - maxFreq > k) {
freq.put(s.charAt(l), freq.get(s.charAt(l)) - 1);
l++;
}
// Update the maximum length of the substring
res = Math.max(res, r - l + 1);
}
return res;
}
public static void main(String[] args) {
int k = 2;
String s = "ABABA";
System.out.println("Maximum length = " + longestSubstr(s, k));
k = 4;
s = "HHHHHH";
System.out.println("Maximum length = " + longestSubstr(s, k));
}
}
def longest_substr(s, k):
n = len(s)
freq = {}
maxFreq = 0
res = 0
l = 0 # Left boundary of the window
# Right boundary of the window
for r in range(n):
# Increase the frequency of the
# current character
freq[s[r]] = freq.get(s[r], 0) + 1
# Update maxFreq with the frequency of
# the most frequent character in the
# current window
maxFreq = max(maxFreq, freq[s[r]])
# Shrink the window if more than k changes
# required
if r - l + 1 - maxFreq > k:
freq[s[l]] -= 1
l += 1
# Update the maximum length of the substring
res = max(res, r - l + 1)
return res
if __name__ == "__main__":
k = 2
s = "ABABA"
print("Maximum length =", longest_substr(s, k))
k = 4
s = "HHHHHH"
print("Maximum length =", longest_substr(s, k))
using System;
using System.Collections.Generic;
class GfG
{
static int LongestSubstr(string s, int k)
{
int n = s.Length;
Dictionary<char, int> freq = new Dictionary<char, int>();
int maxFreq = 0;
int res = 0;
int l = 0; // Left boundary of the window
// Right boundary of the window
for (int r = 0; r < n; ++r)
{
// Increase the frequency of the
// current character
if (!freq.ContainsKey(s[r]))
freq[s[r]] = 0;
freq[s[r]]++;
// Update maxFreq with the frequency of
// the most frequent character in the
// current window
maxFreq = Math.Max(maxFreq, freq[s[r]]);
// Shrink the window if more than k changes
// required
if (r - l + 1 - maxFreq > k)
{
freq[s[l]]--;
l++;
}
// Update the maximum length of the substring
res = Math.Max(res, r - l + 1);
}
return res;
}
static void Main(string[] args)
{
int k = 2;
string s = "ABABA";
Console.WriteLine("Maximum length = " + LongestSubstr(s, k));
k = 4;
s = "HHHHHH";
Console.WriteLine("Maximum length = " + LongestSubstr(s, k));
}
}
function longestSubstr(s, k) {
let n = s.length;
let freq = {};
let maxFreq = 0;
let res = 0;
let l = 0; // Left boundary of the window
// Right boundary of the window
for (let r = 0; r < n; ++r) {
// Increase the frequency of the
// current character
freq[s[r]] = (freq[s[r]] || 0) + 1;
// Update maxFreq with the frequency of
// the most frequent character in the
// current window
maxFreq = Math.max(maxFreq, freq[s[r]]);
// Shrink the window if more than k changes
// required
if (r - l + 1 - maxFreq > k) {
freq[s[l]]--;
l++;
}
// Update the maximum length of the substring
res = Math.max(res, r - l + 1);
}
return res;
}
// Driver code
function main() {
let k = 2;
let s = "ABABA";
console.log("Maximum length =", longestSubstr(s, k));
k = 4;
s = "HHHHHH";
console.log("Maximum length =", longestSubstr(s, k));
}
main();
Output
Maximum length = 5 Maximum length = 6