Code Characters

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.

• 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[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.