Header Ads Widget

Holiday Season | Hackerearth Solution

  Problem:-

It's a holiday season for all school students around the world! Unfortunately, Mahamba is busy preparing for International Olympiad in Informatics, which will be held in Tehran, Iran. He is now facing a new challenge from his teacher Aceka, and it goes something like this:

You have a string x of length N, which consists of small English letters. You have to find the number of indexes abc and d, such that 1<=a<b<c<d<=N and xa==xc, as well as xb==xd.

He is baffled and definitely needs some help. So, you, the best programmer in Lalalandia, decided to give him a hand!

Input format

The first line contains the number N - the length of a string x. The second line contains the string x itself.

Output format

The first and only line should contain the answer to the problem.

Constraints

1<=N<=2000

The string x only contains small English letters.

Sample Input
5
ababa
Sample Output
2
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

There are only 2 variants: (a=1,b=2,c=3,d=4) and (a=2,b=3,c=4,d=5)

 Code:-

Solution 1 ( C language):-

#include<stdio.h>
#define ll long long int
int main(){
    ll n,count=0,j=0;
    scanf("%lld",&n);
    char str[n];
    scanf("%s",str);
    ll alpha[26]={0};
    for(int i=0;i<n;i++){
        ll c=0;
        for(j=i+1;j<n;j++){
            if(str[i]==str[j]){
                count += c;
            }
            c += alpha[str[j]-'a'];
        }
        alpha[str[i]-'a']++;
        
    }
    printf("%ld",count);
    return 0;
}

Solution 2 ( C++ language):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define deb(x) cout << #x << " = " << x << endl;
void getRes()
{
ll n; cin>>n;
string s; cin>>s;
ll alpha[26] = {0}, ans = 0;
for(int i = 0; i < n; i++)
{
ll c = 0;
for(int j = i+1; j < n; j++)
{
if(s[i] == s[j])
{
ans += c;
}
c += alpha[s[j] - 'a'];
}
alpha[s[i] - 'a']++;
}
cout<<ans<<endl;
}
int main()
{
int testCases = 1;
// cin>>testCases;
while (testCases-- > 0)
{
getRes();
}
return 0;
}

Solution 3 (java language):-

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
// Write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
char[] s = br.readLine().toCharArray();
int[] count = new int[26];
long ans = 0;
for(int i=0; i<n; i++){
int curr = 0;
for(int j=i+1; j<n; j++){
if(s[i]==s[j]){
ans += curr;
}
curr += count[s[j]-'a'];
}
count[s[i]-'a']++;
}
System.out.println(ans);
}
}

keywords:-

divide the digits hackerearth solution,alice and strings hackerearth solution,breaking a string hackerearth solution,hackerearth string problems,interesting sum hackerearth solution,
counting frog paths hackerearth solution,popular shop problem hackerearth,policemen and thieves hackerearth solutions,

Recommended Post:-

Post a Comment

0 Comments