Header Ads Widget

Cannibal Characters | hackerearth practice problem

Rajnish Tripathi 22:09

  Problem:-

  You are given an integer n and a string s of size n composed of lower case english letters.

You can perform the following operation on it:

  • In one operation, you have to choose any character in the string s, then delete the first character to the left of the chosen character that is equal to the chosen character (if there exists) and delete the first character to the right of the chosen character that is equal to the chosen character (if there exists). 
  • Note that in one operation, the length of the string s is reduced by a maximum of two characters.

Task

You want to minimize the length of the string s.

Find the minimum number of operations that need to be performed to minimize the length of the string s.

Note:

  • Assume 1 based indexing.

Example

Assumptions :

  • n = 4
  • s = "abaa" (without quotes)

Approach:

  • Choose 3rd character in the string for 1st operation, this will delete the 1st character and 4th character in string s, the string becomes "ba".
  • The length of the string s can not be reduced further.
  • Hence, minimum number of operations needed to reduce the length of the string s to a minimum is 1.

Function Description

Complete the Minimum_Operations function provided in the editor. This function takes the following 2 parameters and returns the required answer:

  • n: Represents the length of string s.
  • s: Represents the string s.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

  • The first line contains a single integer T, which denotes the number of test cases. T also specifies the number of times you have to run the Minimum_Operations function on a different set of inputs.
  • For each test case:
    • First line contains an integer n.
    • Second line contains a string s.

Output format

For each test case in a new line, print the minimum number of operations required to minimize the length of string s.

Constraints

1≤T≤101≤n≤105s contains lowercase english characters

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.

 

Sample Input
2
7
babbaaa
3
abc
Sample Output
3
0
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For first test case:

Given

  • n = 7
  • s = "babbaaa" (without quotes)

Approach:

  • Choose 3rd character in the string for 1st operation, this will delete the 1st character and 4th character in string s, the string becomes "abaaa".
  • Choose 3rd character in the string for 2nd operation, this will delete the 1st character and 4th character in string s, the string becomes "baa".
  • Choose 3rd character in the string for 3rd operation, this will delete the 2nd character in string s, the string becomes "ba".
  • The length of the string s can not be reduced further.
  • Hence, the minimum number of operations needed to reduce the length of the string s to a minimum is 3.

For second test case:

Given

  • n = 3
  • s = "abc" (without quotes)

Approach:

  • The length of the string s can not be reduced further.
  • Hence, the minimum number of operations needed to reduce the length of the string s to a minimum is 0.

10

Code:-

  Here I am going to give you two solution first one is on the basis of C language and second one is on the basis of c++ language which you can submit in c++14 and c++17 also

Solution 1 ( C language):-

#include<stdio.h>
#include<stdbool.h>
#include<malloc.h>
int Minimum_Operations (int n, char* s) {
int sum=0,i;
int a[26]={0};
for(i=0;i<n;i++){
a[s[i]-'a']++;
}
for(i=0;i<26;i++){
sum+=a[i]/2;
}
return sum;
}
int main() {
int T;
scanf("%d", &T);
for(int t_i = 0; t_i < T; t_i++)
{
int n;
scanf("%d", &n);
char* s = (char*)malloc((n+1) * sizeof(char));
scanf("\n%[^\n]s", s);
int out_ = Minimum_Operations(n, s);
printf("%d", out_);
printf("\n");
}
}

Solution 2 ( C++ language):-

 This solution is based on the c++ language and you can submit ib c++14 and c++17 also.
In this solution first three lines of the main function is only for the decreasing the time of execution of the program..
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

This is your choice that you want to use this or not but in some cases the code may take more time in execution and that time we need it .

#include<bits/stdc++.h>
using namespace std;
int Minimum_Operations (int n, string s) {
// Write your code here
vector<int>cnt(26,0);
for(auto i:s)
{
cnt[i-'a']++;
}
int ans=0;
for(auto i:cnt)
{
ans+=(i/2);
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for(int t_i = 0; t_i < T; t_i++)
{
int n;
cin >> n;
string s;
cin >> s;
int out_;
out_ = Minimum_Operations(n, s);
cout << out_;
cout << "\n";
}
}

keywords:-

,cannibal characters hackerearth solution,cannibal character in silence of the lambs,cannibal characters in video games,

,wrong turn cannibal characters,

,anime cannibal characters,

,dnd cannibal character,

,lego pirates cannibal character,

,cannibal holocaust characters,

,cannibal crossing characters,

,cannibal anime characters,

,cannibalism in the cars characters,

,cannibal movie characters,

,cannibal ferox characters,

,cannibal the musical characters,

,cannibalistic characters,

,cannibal in chinese characters,

,cannibals main characters,

Recommended Post:

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags: