How does The Interns Company match students with internships?

We use a combination of AI-powered matching algorithms and human expertise to connect students with internship opportunities that align with their skills, interests, and career goals.

Are the internship opportunities exclusive?

Yes, many of our partner companies offer positions exclusively through our platform that you won't find on public job boards or career sites.

Is there a cost to use The Interns Company?

Our basic matching service is free for students. Premium services like one-on-one interview coaching and resume reviews may have associated fees.

Longest Repeating Character Replacement

MediumAcceptance: 49.8%

String Sliding Window

Problem Statement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

Constraints:

1 <= s.length <= 10^5
s consists of only uppercase English letters
0 <= k <= s.length

Input Format:

A string s consisting of uppercase English letters
An integer k

Output Format:

Return an integer representing the length of the longest substring containing the same letter after performing at most k character replacements.

Examples:

Example 1:

Input:

s = "ABAB", k = 2

Output:

Explanation:

Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:

s = "AABABBA", k = 1

Output:

Explanation:

Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

Solutions

Sliding Window Approach

Time: O(n)

Space: O(1)

Use a sliding window technique with a character frequency counter. The window expands as long as we can replace characters (window length - most frequent char count ≤ k). When we exceed k replacements, we shrink the window from the left.

Optimized Sliding Window

Time: O(n)

Space: O(1)

An optimization where we don't need to recalculate the maximum frequency when shrinking the window.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

Initialize charCount = {}, maxFreq = 0, left = 0, result = 0
right=0: s[0]='A', charCount={'A':1}, maxFreq=1, window='A', result=1
right=1: s[1]='A', charCount={'A':2}, maxFreq=2, window='AA', result=2
right=2: s[2]='B', charCount={'A':2,'B':1}, maxFreq=2, window='AAB', result=3
right=3: s[3]='A', charCount={'A':3,'B':1}, maxFreq=3, window='AABA', result=4
right=4: s[4]='B', charCount={'A':3,'B':2}, maxFreq=3, window='AABAB', need 2 replacements but k=1, shrink window
After shrinking: left=1, window='ABAB', charCount={'A':2,'B':2}, maxFreq=2, need 2 replacements but k=1, shrink window
After shrinking: left=2, window='BAB', charCount={'A':1,'B':2}, maxFreq=2, need 1 replacement which is ≤ k, result=3
right=5: s[5]='B', charCount={'A':1,'B':3}, maxFreq=3, window='BABB', result=4
right=6: s[6]='A', charCount={'A':2,'B':3}, maxFreq=3, window='BABBA', need 2 replacements but k=1, shrink window
After shrinking: left=3, window='BBA', charCount={'A':1,'B':2}, maxFreq=2, need 1 replacement which is ≤ k, result=3
Final result: 4

Hints

Hint 1

Think about using a sliding window approach to solve this problem.

Hint 2

Keep track of the character frequency in the current window.

Hint 3

The key insight is to track the most frequent character in the current window.

Hint 4

If (window length - count of most frequent character) > k, then we need to shrink the window from the left.

Video Tutorial