Last Updated on March 29, 2022 by Ria Pathak

### Concepts Used

String

### Difficulty Level

Easy

### Problem Statement (Simplified):

Find the minimum length of substring, which on replacing with any other substring of the same length gives a string containing all characters in the same frequency. String only contains letters

`C`

,`O`

,`D`

, and`E`

.

**See original problem statement here**

#### Test Case

```
Input:
3
CODE
CCOD
EDDCDCEE
Output:
0
1
2
Explanation:
Case-1:
S is already balanced.
Case-2:
We need to replace a 'C' to 'E' so that "CEOD" (or "ECOD") is balanced.
Case-3:
We need to replace 'ED' to 'OO' so that "OODCDCEE" is balanced.
```

### Solving Approach :

1) To maintain the frequency of characters, we use hashing technique that uses a hash table.

A hash table is an array, where each index represents aHash Table:Keyand value at index representsvalueassociated with the key.2) We use

`Sliding`

`Window`

method to calculate minimum window length which contains all character less than a quarter of the length of string, we keep counting string length until any of the characters becomes more than a quarter of length which means.

3) In the window we don’t consider the character of the left pointer as part of characters.

4) We increment the right pointer by 1 if the string contains all character less than a quarter of string length.

5) After our left pointer has crossed string length, we print the minimum length saved.

### Example

Let’s assume string to check is

`"EDDCDCEE"`

, length of the string is`8`

and its quarter value will be`2`

. So every character must appear twice in target string.Here we can see excluding window from

`1`

to`0`

and replacing it with 2`O`

‘s can make string balance.Our current window size is

`2`

. We window further for more indexes.Window from

`1`

to`6`

,`2`

to`6`

,`2`

to`3`

, and`4`

to`6`

are also such windows, thus we check if it is smaller than the current window size, and we update minimum window size.From above we can see minimum window size is

`2`

. So, we print`2`

as our answer.

### Solutions

#include <stdio.h> #include <string.h> int main() { int test; scanf("%d",&test); while(test--){ char s[999999]; scanf("%s",s); int hash[26] = {0}, len = strlen(s), finalLen = len; int j=0, def = len/4; for(int i=0; i<len; i++) hash[s[i]-'A']++; for(int i=0; i<len; i++){ hash[s[i]-'A']--; while(j < len && hash['C'-'A'] <= def && hash['O'-'A'] <= def && hash['D'-'A'] <= def && hash['E'-'A'] <= def){ finalLen = (finalLen<i-j+1) ? finalLen : i-j+1; hash[s[j++]-'A']++; } } printf("%d\n",finalLen); } }

#include <bits/stdc++.h> using namespace std; int main() { int test; cin>>test; while(test--){ char s[999999]; cin>>s; int hash[26] = {0}, len = strlen(s), finalLen = len; int j=0, def = len/4; for(int i=0; i<len; i++) hash[s[i]-'A']++; for(int i=0; i<len; i++){ hash[s[i]-'A']--; while(j < len && hash['C'-'A'] <= def && hash['O'-'A'] <= def && hash['D'-'A'] <= def && hash['E'-'A'] <= def){ finalLen = min( finalLen, i-j+1 ); hash[s[j++]-'A']++; } } cout<<finalLen<<endl; } }

import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int test = sc.nextInt(); while(test-->0){ String s = sc.next(); int hash[] = new int[26], len = s.length(), finalLen = len; int j=0, def = len/4; for(int i=0; i<len; i++) hash[s.charAt(i)-'A']++; for(int i=0; i<len; i++){ hash[s.charAt(i)-'A']--; while(j < len && hash['C'-'A'] <= def && hash['O'-'A'] <= def && hash['D'-'A'] <= def && hash['E'-'A'] <= def){ finalLen = (finalLen<i-j+1) ? finalLen : i-j+1; hash[s.charAt(j++)-'A']++; } } System.out.println(finalLen); } } }

for _ in range(int(input())): s = input() hash = [0] * 26 l = len(s) finalLen = l j = 0 def_ = l//4 for i in range(l): hash[ord(s[i]) - ord("A")] += 1 for i in range(l): hash[ord(s[i]) - ord("A")] -= 1 while(j < l and hash[ord('C') - ord('A')] <= def_ and hash[ord('O') - ord('A')] <= def_ and hash[ord('D') - ord('A')] <= def_ and hash[ord('E') - ord('A')] <= def_): finalLen = min( finalLen, i-j+1 ) hash[ord(s[j]) - ord('A')] += 1 j += 1 print(finalLen)

**Space Complexity** of this approach would be `O(1).`

[forminator_quiz id="1189"]

This article tried to discuss **Strings**. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming.