Header Ad

HackerRank Beautiful Strings problem solution

In this HackerRank Beautiful Strings problem solution, we have given a string S consisting of lowercase English letters. a string is beautiful with respect to S if it can be derived from S by removing exactly 2 characters. and we need to find and print the number of different strings that are beautiful with respect to S.

HackerRank Beautiful Strings problem solution


Problem solution in Python.

import itertools
s = input()
groups = [(c, sum(1 for x in l)) for c, l in itertools.groupby(s)]
multiple = sum(x[1] > 1 for x in groups)
fence = sum(groups[i - 1][0] == groups[i + 1][0] and groups[i][1] == 1 \
            for i in range(1, len(groups) - 1))
print(multiple + len(groups) * (len(groups) - 1) // 2 - fence)


Problem solution in Java.

import java.io.*;

public class Solution {
    
  static long beautifulStrings(char[] s) {
      long result = 0;
      int res[] = new int[s.length];
      for (int j = s.length-1; j > 0; j--) {
          res[j-1] = res[j];
          if ((j > 1) && (s[j] == s[j-1])) {
              continue;
          }
          res[j-1]++;
          result++;
      }
      for (int i = 1; i < s.length-1; i++) {
          if (s[i] == s[i-1]) {
              continue;
          }
          if (s[i+1] != s[i-1]) {
            result++;
          }
          result += res[i+1];
      }
      return result;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
    char[] s = br.readLine().toCharArray();

    long result = beautifulStrings(s);
    bw.write(String.valueOf(result));
    bw.newLine();

    bw.close();
    br.close();
  }
}

{"mode":"full","isActive":false}


Problem solution in C++.

#include <bits/stdc++.h>

#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair
#define sz(a) int((a).size())
#ifdef _WIN32
#  define I64 "%I64d"
#else
#  define I64 "%lld"
#endif
#define fname "."

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = (int)1e5 + 123;
const double eps = 1e-6;
const int inf = (int)1e9 + 123;

using namespace std;

string s;
ll ans;

ll slow() {
	set < string > q;
	for (int i = 0; i < sz(s); i++)
		for (int j = i + 1; j < sz(s); j++) {
			string nw = "";
			for (int k = 0; k < sz(s); k++)
				if (k != i && k != j)
					nw += s[k];
			q.insert(nw);
		}
	return sz(q);
}

int main() {
	#ifdef Nick
	freopen(fname"in","r",stdin);
	freopen(fname"out","w",stdout);
	#endif
	cin >> s;
	for (int i = 1, len = 1, cnt = 1; i <= sz(s); i++) {
		if (i == sz(s) || s[i] != s[i - 1]) {
			ans += (cnt - 1) + (len > 1);
			len = 1;
			cnt++;
		}
		else
			len++;
	}	
	for (int i = 0; i + 1 < sz(s); ) {
		if (s[i] == s[i + 1]) {
			i++;
			continue;
		}
		int len = 2;
		while(i + len < sz(s) && s[i + len] == s[i + (len % 2)])
			len++;
		ans -= (len - 2);
		i += len - 1;
	}
	cout << ans;
	return 0;
}

{"mode":"full","isActive":false}


Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

/*
 * Complete the beautifulStrings function below.
 */
long beautifulStrings(char* s) {
    /*
     * Write your code here.
     */
    int a,f,x=0,i,j;
    f=strlen(s);
    a=(f*(f-1))/2;
    for(i=0;i<f;i++){
        for(j=i+1;j<f;j++){
            if(s[i]==s[j]){
                x++;
            }
        }

    }
    return a-x;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* s = readline();

    long result = beautifulStrings(s);

    fprintf(fptr, "%ld\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

{"mode":"full","isActive":false}


Post a Comment

0 Comments