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

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.

Leave a Reply

Your email address will not be published. Required fields are marked *