Longest substring having all same characters after k changes

Last Updated : 16 Jun, 2025

We have a string of length n, which consist only UPPER English alphabet characters and we have a number k (always less than n and greater than 0). We can make at most k changes in our string such that we can get a longest substring of the same character repeating.

Examples:

Input : k = 2, s = ABABA
Output : 5
We can get maximum length by replacing 2 B's with A's
Input : k = 4, s = HHHHHH
Output : 6
We get maximum length 6 without any replacement

Table of Content

Naive Solution - O(n^3) Time
Expected Approach 1 - Window Sliding for Every Character - O(26 * n) Time
Expected Approach 2 - Window Sliding with Hash Map - O(n) Time

Naive Solution - O(n^3) Time

Consider every susbtring and find if it can have all characters same with K changes. If yes, then update the result if its length is more. To check if the substring can can be converted to all same characters, we find the most frequent character.

C++

#include <iostream>
#include <unordered_map>
using namespace std;

// function to get the maximum frequency of 
// any character in the substring [l, r]
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;
}

// Driver code
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>

// Function to get the maximum frequency of 
// any character in the substring [l, r]
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;
}

// Driver code
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;
}

Java

import java.util.HashMap;

// Function to get the maximum frequency of 
// any character in the substring [l, r]
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));
    }
}

Python

# Function to get the maximum frequency of 
# any character in the substring [l, r]
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

# Driver code
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 {
  
    // Function to get the maximum frequency of 
    // any character in the substring [l, r]
    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));
    }
}

JavaScript

// Function to get the maximum frequency of 
// any character in the substring [l, r]
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

Time Complexity: O(n^3)
Auxiliary Space: O(1)

**Expected Approach 1 - Window Sliding for Every Character - O(26 * n) Time**

We check for each character of English alphabet one by one We are basically looking for maximum length of sub-string that can be formed with each character being the only character after at-most k changes. Whichever character gives us the maximum length, we return that as result

We check for maximum length of sub-string that can be formed by every character in a set of 26 characters (From 'A' to 'Z').
For doing this we traverse whole string and whenever we find a different character, we increase the count.
If count becomes greater than k (at right index), we decrease the count and remove leftmost character from the current window.
We finally return the maximum length.

C++

#include <iostream>
using namespace std;

// function which returns maximum length of substring
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;
}

// Driver code
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>

// Function which returns maximum length of substring
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;
}

// Driver code
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;
}

Java

import java.util.*;

class GfG {

    // function which returns maximum length of substring
    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;
    }

    // Driver code
    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));
    }
}

Python

# Function which returns maximum length of substring
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

# Driver code
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 {

    // function which returns maximum length of substring
    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;
    }

    // Driver code
    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));
    }
}

JavaScript

// Function which returns maximum length of substring
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

Time Complexity: O(n)
Auxiliary Space: O(1)

Expected Approach 2 - Window Sliding with Hash Map - O(n) Time

This solution uses ideas from both of the previous approaches. We maintain a window and inside the window, we maintain frequency of the most frequent character. To find and maintain the most frequent character, we use hash map. Below are the detailed steps.

We maintain a window between indices l and r. The window slides to the right, expanding or contracting depending on the number of changes needed to make all characters the same.
We keep track of the most frequent character in the current window.
If the number of characters that need to be changed (r - l + 1 - maxFreq) exceeds k, we shrink the window by moving the left boundary l to the right. Else we keep expanding the window on right side.

C++

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to find the maximum length of substring
// with at most k changes
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;
}

// Driver code
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>

// Function to find the maximum length of substring
// with at most k changes
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;
}

// Driver code
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;
}

Java

import java.util.HashMap;

class GfG {

    // Function to find the maximum length of substring
    // with at most k changes
    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;
    }

    // Driver code
    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));
    }
}

Python

# Function to find the maximum length of substring
# with at most k changes
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

# Driver code
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
{
    // Function to find the maximum length of substring
    // with at most k changes
    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;
    }

    // Driver code
    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));
    }
}

JavaScript

// Function to find the maximum length of substring
// with at most k changes
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

Time Complexity: O(n)
Auxiliary Space: O(1)

niteesh_Kr

Improve

Article Tags :

Longest substring having all same characters after k changes

Naive Solution - O(n^3) Time

Expected Approach 1 - Window Sliding for Every Character - O(26 * n) Time

Expected Approach 2 - Window Sliding with Hash Map - O(n) Time

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem

Thank You!

What kind of Experience do you want to share?

**Expected Approach 1 - Window Sliding for Every Character - O(26 * n) Time**