Concepts Used:

Strings, Basic Mathematics

Difficulty Level:

Easy

Problem Statement (Simplified):

Print the maximum length of string which can be formed such that the number of a is more than half of its total length. You can form new string by removing characters from given string.

See original problem statement here

Test Case:

Input:
1
xaxxxxa

Output:
3

Explanation:
Here string is of length 7 and there are 2 a's in the string.
If we want a's to be more than half, we'll add 1 extra character, so the length of the smallest string would be 3.

Solving Approach :

1) Learn programming languages online and We can solve it by counting the number of appearances of a.
2) If the count is already more than half we don’t have to delete any character, the string’s current length is already at maximum.
3) If the count is less than half, Let’s say the count of a be C. So, maximum length of string will be ( 2 x ( C – 1 ) ) + 1.

Example:

  • Assuming string to be ‘astrangeanalogy‘, having length 15 and there are 4 a‘s in the string. So we would need a string containing 4 a‘s.
  • As the count of a‘s in the new string should be more than half, which means if we remove one a from the number of a‘s in new string, size of new string will be double of the number of a‘s in new string. So we add a single a we removed earlier . So we use this and we find that size of the string will be 7.
    minSize = ((countOfA - 1) x 2) + 1

Solutions:

#include <stdio.h>
#include<string.h>
int main()
{
  int test;
  scanf("%d", &test);

  while(test--){

    char s[10000000];
    scanf("%s", s);

    int count=0;

    for(int i=0; i<strlen(s); i++)
        if(s[i]=='a')
            count++;
    if(count > strlen(s)/2)
      printf("%d\n",strlen(s));
    else{
      printf("%d\n",(count-1)*2 + 1);
    }
  }
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int test;
  cin>>test;

  while(test--){

    string s;
    cin>>s;

    int count=0;

    for(int i=0; i<s.length(); i++)
        if(s[i]=='a')
            count++;
    if(count > s.length()/2)
      cout<<s.length()<<endl;
    else{
      cout<<(count-1)*2 + 1<<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_cases;
     test_cases = sc.nextInt();

     while(test_cases != 0){

         String s = sc.next();

         int count=0;

         for(int i=0; i<s.length(); i++)
             if(s.charAt(i)=='a')
                 count++;
         if(count > s.length()/2)
           System.out.println(s.length());
         else{
           System.out.println((count-1)*2 + 1);
         }

         test_cases--;
     }
   }
 }
Previous post Minimum number of operations to make string palindrome
Next post Convert Integer number to Roman Number

Leave a Reply

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