  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Code Characters

Last Updated on March 29, 2022 by Ria Pathak String

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:

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.

• Hash Table: A hash table is an array, where each index represents a Key and value at index represents value associated 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;
scanf("%s",s);

int hash = {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;
cin>>s;

int hash = {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, 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 =  * 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.