HackerRank String Construction Problem Solution

In this post, we will solve HackerRank String Construction Problem Solution.

Amanda has a string of lowercase letters that she wants to copy to a new string. She can perform the following operations with the given costs. She can perform them any number of times to construct a new string p:

Append a character to the end of string p at a cost of 1 dollar.
Choose any substring of p and append it to the end of p at no charge.
Given n strings s[i], find and print the minimum cost of copying each s[i] to p[i] on a new
line.
For example, given a strings = abcabc, it can be copied for 3 dollars. Start by copying a, b and c individually at a cost of 1 dollar per character. String p = abc at this time. Copy p[0: 2] to the end of p at no cost to complete the copy

Function Description

Complete the stringConstruction function in the editor below. It should return the minimum cost of copying a string.

stringConstruction has the following parameter(s):

s: a string

Input Format
The first line contains a single integer n, the number of strings.
Each of the next lines contains a single string, s[i].

Output Format

For each string s[i] print the minimum cost of constructing a new string p[i] on a new line.

Sample Input

2
abcd
abab

Sample Output

4
2

Explanation
Query 0: We start with 8 = “abcd” and p = “”.

Append character ‘a’ to p at a cost of 1 dollar, p = “a”.
Append character ‘b’ to p at a cost of 1 dollar, p = “ab”.
Append character ‘c’ to p at a cost of 1 dollar, p = “abc”.
Append character ‘d’ to p at a cost of 1 dollar, p = “abcd”.
Because the total cost of all operations is 1+1+1+1 = 4 dollars, we print 4 on a new
line.
Query 1: We start with 8 = “abab” and p = “”,
Append character ‘a’ to p at a cost of 1 dollar, p = “a”.
Append character ‘b’ to p at a cost of 1 dollar, p = “ab”.
Append substring “ab” to p at no cost, p= “abab”.
Because the total cost of all operations is 1 + 1 = 2 dollars, we print 2 on a new line.

HackerRank String Construction Problem Solution

String Construction C Solution

#include <stdio.h>
#include <stdlib.h>

int main(){
    
    int LetterCount = 'z' - 'a' + 1;
    char GotLetter[LetterCount];
    
    int i, j, n, cost; 
    char c;
    
    scanf("%d",&n);
    fgetc(stdin);
    
    for(i=0; i<n ;i++){
        cost = 0;
        for(j=0; j<LetterCount; j++){
           GotLetter[j] = 0;
        }
        
        while(1){
            c = fgetc(stdin);
            if(c == EOF || c == '\n'){
                break;
            }
            
            if(!GotLetter[c - 'a']){
                GotLetter[c - 'a'] = 1;
                cost++;
            }
        }
        
        printf("%d\n", cost);
    }
    
    return 0;
}

String Construction C++ Solution

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int ctr1=0;ctr1<n;ctr1++){
        string s;
        int ar[26];
        memset(ar,0,sizeof(ar));
        cin>>s;
        for(int ctr2=0;ctr2<s.length();ctr2++)
            ar[s[ctr2]-'a']++;
        int rez=0;
        for(int ctr2=0;ctr2<26;ctr2++)
            rez+=ar[ctr2]>0;
        cout<<rez<<"\n";
    }
    return 0;
}

String Construction C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
            int n = Int32.Parse(Console.ReadLine().Trim());

            byte aCode = Convert.ToByte( 'a' );

            for(int t = 0; t < n; ++t)
            {
                byte[] bytes = System.Text.Encoding.Default.GetBytes( Console.ReadLine().Trim() );
                

                bool[] letter = new bool[26];
                int count = 0;
                for (int i = 0; i < bytes.Length; ++i)
                {
                    if (!letter[ bytes[ i ] - aCode ]) ++count;
                    letter[ bytes[ i ] - aCode ] = true;
                }

                Console.WriteLine( count );
            }
    }
}

String Construction Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'stringConstruction' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int stringConstruction(String s) {
    // Write your code here
        return (int) (s.chars().distinct().count());
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String s = bufferedReader.readLine();

                int result = Result.stringConstruction(s);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

String Construction JavaScript Solution

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////
function totalCost(str) {
    if(str === '' || str.length === 0 || str === undefined || str === null) return 0;
    var p = '';
    var cost = 0;
    for(var i = 0, j = str.length; i < j; i++) {
        if(p.indexOf(str[i]) === -1) {
            cost++;
            p += str[i];
        } else p += str[i];
    }
    return cost;
}
function main() {
    var n = parseInt(readLine());
    for(var a0 = 0; a0 < n; a0++){
        var s = readLine();
        console.log(totalCost(s));
    }

}

String Construction Python Solution

#!/bin/python3

import sys


n = int(input().strip())
for a0 in range(n):
    s = input().strip()
    knownLetters = []
    for el in s:
        if not (el in knownLetters):
            knownLetters.append(el)
    print (len(knownLetters))