HackerRank Build a String Problem Solution

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

Greg wants to build a string, S of length N. Starting with an empty string, he can perform 2
operations:

Add a character to the end of $ for A dollars.
Copy any substring of S, and then add it to the end of $ for B dollars.
Calculate minimum amount of money Greg needs to build S.
Input Format
The first line contains number of testcases T.
The 2 x T subsequent lines each describe a test case over 2 lines: The first contains 3 space-separated integers, N. A, and B, respectively. The second contains S (the string Greg wishes to build).

Output Format

On a single line for each test case, print the minimum cost (as an integer) to build S.

Sample Input

2
9 4 5
aabaacaba
9 8 9
bacbacacb

Sample Output

26
42

Explanation
Test Case 0:
Sinitial=””; Sfinal = “aabaacaba”
Append “a”: S = “a”; cost is 4
Append “a”: S = “aa”: cost is 4
Append “b”; S = “aab”; cost is 4 5
Copy and append “aa”: S = “aabaa”; cost is
Append “c”; S = “aabaac”; cost is 4
Copy and append “aba”: S = “aabaacaba”; cost is 5
Summing each cost, we get 4 +4 +4 +5+4+5= 26, so our output for Test Case 1 is
26.
Test Case 1:
Sinitial “Sfinal “bacbacacb” =
Append “b”: S = “b”; cost is $8
Append “a”: S = “ba”; cost is $8
Append “c”: S = “bac”; cost is $8
Copy and append “bac”: S = “bacbac”: cost is $9
Copy and append “acb”: S = “bacbacacb”; cost is $9
Summing each cost, we get 8 +8 +8 +9 +9 42, so our output for Test Case 2 is 42.

Table of Contents

Build a String C Solution

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

char* readline();
char** split_string(char*);

/*
 * Complete the buildString function below.
 */
int** idx(int n, char* s) {
    int** i = malloc(sizeof(int*) * 26);
    int a;

    for(int j=0;j<26;j++) {
        i[j] = malloc(sizeof(int) * 1);
        i[j][0] = 0;
    }
    
    for(int j=0;j<n;j++) {
        a = s[j] - 'a';
        i[a] = realloc(i[a], sizeof(int) * ++i[a][0] + 1);
        i[a][i[a][0]] = j;
    }
    return i;
}

int greedy(int n, int start, int** index, char* s) {
    int best = 0;
    int offset, i;
    int* x = index[s[start]-'a'];
    int sz = x[0];

    for(int j=1;j<sz;j++) {
        i = x[j];

        if(best >= n-i || i + best >= start)
            break;

        offset = 1;
        while (i + offset < start && start + offset < n 
            && s[i + offset] == s[start + offset])
            ++offset;

        if(offset > best)
            best = offset;
    }

    return best;
}

int buildString(int n, int a, int b, char* s) {
    int** x = idx(n, s);
    int c[n];
    c[0] = a;

    for(int i = 1; i < n; i++)
        c[i] = INT_MAX;

    int A,B,G;
    for(int i = 1, j=0; i < n; i++) {
        A = c[i-1] + a;
        B = c[i-1] + b;
        G = greedy(n, i, x, s);

        if(c[i] > A) 
            c[i] = A;

        if(G > 1) {
            j = i + G - 1;
            if(c[j] > B) 
                c[j] = B;
        }
    }
    return c[n-1];
}

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

    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int t_itr = 0; t_itr < t; t_itr++) {
        char** nab = split_string(readline());

        char* n_endptr;
        char* n_str = nab[0];
        int n = strtol(n_str, &n_endptr, 10);

        if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

        char* a_endptr;
        char* a_str = nab[1];
        int a = strtol(a_str, &a_endptr, 10);

        if (a_endptr == a_str || *a_endptr != '\0') { exit(EXIT_FAILURE); }

        char* b_endptr;
        char* b_str = nab[2];
        int b = strtol(b_str, &b_endptr, 10);

        if (b_endptr == b_str || *b_endptr != '\0') { exit(EXIT_FAILURE); }

        char* s = readline();

        int result = buildString(n, a, b, s);
        fprintf(fptr, "%d\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;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

Build a String C++ Solution

#include <bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
typedef pair<int, int> pii;
const int inf = 1 << 30;
const int N = 4e4;
const int L = 20;
int rmq[N][L];
int p[N][L];
int dp[N];
int s[N];
int lgx;
int tc;
int n;
int a;
int b;
string T;

struct Tuple {
  pii p;
  int id;
} l[N];

void input() {
  cin >> n >> a >> b >> T;
  memset(dp, 127, sizeof dp);
  for (int i = 0; i < n; ++i) {
    p[i][0] = T[i];
  }
}

void prepr() {
  for (int i = 0; i < n; ++i) {
    rmq[i][0] = s[i];
  }
  for (int j = 1; j < L; ++j) {
    for (int i = 0; i + (1 << j) <= n; ++i) {
      rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
    }
  }
}

int lcp(int i, int j) {
  int res = 0;
  for (int k = lgx; k >= 0 && i < n && j < n; --k) {
    if (p[i][k] == p[j][k]) {
      i += (1 << k);
      j += (1 << k);
      res += (1 << k);
    }
  }
  return res;
}

int lg(int x) { return 31 - __builtin_clz(x); }

int query(int x, int y) {
  int logx = lg(y - x + 1);
  return min(rmq[x][logx], rmq[y - (1 << logx) + 1][logx]);
}

int left(int i, int x, int y, int k) {
  if (x == y) {
    return s[i - x];
  }
  int q = x + y >> 1;
  int mnm = query(i - q, i);
  if (mnm <= k) {
    return left(i, x, q, k);
  } else {
    return left(i, q + 1, y, k);
  }
}

int right(int i, int x, int y, int k) {
  if (x == y) {
    return s[i + x];
  }
  int q = x + y >> 1;
  int mnm = query(i, i + q);
  if (mnm <= k) {
    return right(i, x, q, k);
  } else {
    return right(i, q + 1, y, k);
  }
}

int binsearch(int x, int y, int i) {
  if (x == y) {
    return x;
  }
  int q = x + y + 1 >> 1;
  int j = p[i][lgx];
  int lft = left(j - 1, 0, j, i - q);
  int rgt = right(j + 1, 0, n - j - 1, i - q);
  if (lcp(lft, i) >= q || lcp(rgt, i) >= q) {
    return binsearch(q, y, i);
  } else {
    return binsearch(x, q - 1, i);
  }
}

void solve() {
  for (int i = 1, j = 1; j <= n; ++i, j <<= 1) {
    for (int k = 0; k < n; ++k) {
      l[k].p.xx = p[k][i - 1];
      l[k].p.yy = k + j < n ? p[k + j][i - 1] : -1;
      l[k].id = k;
    }
    sort(l, l + n, [](Tuple x, Tuple y) { return x.p < y.p; });
    p[l[0].id][i] = 0;
    for (int k = 1; k < n; ++k) {
      p[l[k].id][i] = l[k - 1].p == l[k].p ? p[l[k - 1].id][i] : k;
    }
    lgx = i;
  }
  for (int i = 0; i < n; ++i) {
    s[p[i][lgx]] = i;
  }
  prepr();
  dp[0] = a;
  for (int i = 1; i < n; ++i) {
    int k = binsearch(0, i, i);
    dp[i + k - 1] = min(dp[i + k - 1], dp[i - 1] + b);
    dp[i] = min(dp[i], dp[i - 1] + a);
  }
  cout << dp[n - 1] << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> tc;
  while (tc--) {
    input();
    solve();
  }
}

Build a String C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    static bool Debug = false;

    struct AbsPos { public readonly int Value; public AbsPos ( int value ) => Value = value; }
    struct RelPos { public readonly int Value; public RelPos ( int value ) => Value = value; }

    class MatchRun {
        public static string s;

        public readonly AbsPos fromPosition;
        int commonLength;
        List<Tuple<char, MatchRun>> cases;

        public MatchRun( AbsPos pos ) {
            fromPosition = pos;
            commonLength = -1;
            cases = null;
        }

        public MatchRun ( AbsPos pos, int len, List<Tuple<char, MatchRun>> cases ) {
            fromPosition = pos;
            commonLength = len;
            this.cases = cases;
        }

        public MatchRun Match ( char c, ref RelPos relPos, AbsPos absPos ) {
            if ( fromPosition.Value + relPos.Value >= absPos.Value )
                return null;

            if ( commonLength < 0 || relPos.Value < commonLength ) {
                if ( s [ fromPosition.Value + relPos.Value ] == c ) {
                    relPos = new RelPos ( relPos.Value + 1 );
                    return this;
                }
                return null;
            }

            var list = cases;
            for ( int i = 0; i < list.Count; i++ ) {
                var ca = list [ i ];
                if ( ca.Item1 == c ) {
                    relPos = new RelPos ( 1 );
                    return ca.Item2;
                }
            }

            return null;
        }

        public void AddCase ( char c2, RelPos tail, AbsPos pos ) {
            if ( Debug )
                Console.WriteLine ( "Splitting: {0}", this );
            if ( commonLength < 0 ) {
                // rest of string; i.e. not yet split/no cases
                cases = new List<Tuple<char, MatchRun>> ();
                cases.Add ( new Tuple<char, MatchRun> ( s [ fromPosition.Value + tail.Value ], new MatchRun ( new AbsPos ( fromPosition.Value + tail.Value ) ) ) );
                commonLength = tail.Value;
            } else if ( tail.Value < commonLength ) {
                // is already split but further out
                // move existing cases to their own split
                var newsplit = new List<Tuple<char, MatchRun>> ();
                newsplit.Add ( new Tuple<char, MatchRun> ( s [ fromPosition.Value + tail.Value ], 
                                new MatchRun ( new AbsPos ( fromPosition.Value + tail.Value ) , commonLength - tail.Value, cases ) ) );
                // and take over the shorter section from here
                cases = newsplit;
                commonLength = tail.Value;
            }
            cases.Add ( new Tuple<char, MatchRun> ( c2, new MatchRun (  pos ) ) );
            if ( Debug )
                Console.WriteLine ( "...into: {0}", this );
        }

        public override string ToString () {
            if ( commonLength < 0 ) {
                var str = fromPosition.Value.ToString () + "-(" + s [ fromPosition.Value ] + ')';
                return str;
            }
            {
            var str = '[' + fromPosition.Value.ToString () + '-' + commonLength.ToString () + '(' +
                    s.Substring ( fromPosition.Value, commonLength ) + ')';
                for ( int i = 0; i < cases.Count; i++ ) {
                    var c = cases [ i ];
                    str += ' ';
                    str += c.Item1;
                    str += ':';
                    str += c.Item2.ToString ();
                }
                str += ']';
                return str;
            }
        }
    }

    class Duplicate {
        public MatchRun ofWhat;
#if Debug
        public AbsPos absPos;
#endif
        public RelPos tail;

        public Duplicate ( MatchRun ofWhat, RelPos position, AbsPos absPos ) {
            this.ofWhat = ofWhat;
            this.tail = position;
#if Debug
            this.absPos = absPos;
#endif
        }

        public void SetDuplicate ( MatchRun ofWhat, RelPos position, AbsPos absPos ) {
            this.ofWhat = ofWhat;
            this.tail = position;
#if Debug
            this.absPos = absPos;
#endif
        }

        public override string ToString () {
#if Debug
            var str = '<' + absPos.Value.ToString() + '(' + MatchRun.s.Substring ( absPos.Value, 1 ) + "):" + tail.Value.ToString () + "> " + ofWhat.ToString ();
#else
            var str = '<' + "():" + tail.Value.ToString () + "> " + ofWhat.ToString ();
#endif
            return str;
        }
    }

    static int buildString(int a, int b, string s) {
        // a is cost of one character, b is cost of one substring

        /*
         * Solution by Erik L. Eidt (c) 2020, placed into public domain
         */

        int cost = 0;

        int sLength = s.Length;
        if ( a * sLength <= b ) return a*sLength;
        
        MatchRun.s = s;

        var stateTable = new MatchRun [ 26 ];
        var duplicates = new LinkedList<Duplicate> ();
        var dupPool = new LinkedList<Duplicate> ();

        var endCosts = new int [ sLength ];

        if ( Debug )
            Console.WriteLine ( "a={0}, b={1}", a, b );

        for ( int pos = 0; pos < sLength; ) {

            //if ( pos == 999 ) {
            //    int abc = 1;
            //}

            /*
             * Handle next input character
             */

            int maxSubstringLength = 0;
            var ch = s [ pos ];
            
            if ( Debug )
                Console.WriteLine ( "pos={0} ch={1}", pos, ch );

            var rootEnt = stateTable [ ch - 'a' ];
            if ( rootEnt != null ) {
                maxSubstringLength = 1;
                /*
                 * Locate longest match
                 */
                RelPos matchPos = new RelPos ( 1 );
                var ent = rootEnt;
                for ( int i = 1; i < pos && pos + i < sLength; i++ ) {
                    ent = ent.Match ( s [ pos + i ], ref matchPos, new AbsPos ( pos ) );
                    if ( ent == null ) break;
                    maxSubstringLength++;
                }

            if ( Debug )
                Console.WriteLine ( "SS @ {0} Len {1} '{2}' for {3} vs. {4}", pos, maxSubstringLength, 
                    s.Substring ( pos, maxSubstringLength ), b, a * maxSubstringLength );
            }

            /*
             * Compute substring costs and store best-so-far matches at future postions
             */

            int ssCost = cost + b;
            for ( int len = 1; len <= maxSubstringLength; len++ ) {
                int end = pos + len - 1;
                var anEndCost = endCosts [ end ];
                if ( anEndCost == 0 || ssCost < anEndCost ) 
                    endCosts [ end ] = ssCost;
            }

            /*
             * Current best count
             */
            cost += a;

            if ( Debug && false )
                Console.WriteLine ( "AD @ {0} Len {1} '{2}'; cost = {3}", pos, 1, s.Substring ( pos, 1 ), cost );
 
            /*
             * If we hit a better count from a prior substring match, take it in place of current best
             */
            var endCost = endCosts [ pos ];
            if ( endCost != 0 && endCost < cost )
                cost = endCost;

            /*
             * Extend duplicates with ch
             */
            for ( var dupNode = duplicates.First; dupNode != null; ) {
                var dup = dupNode.Value;
                var dupNext = dupNode.Next;
                if ( Debug )
                    Console.WriteLine ( "Checking dup {0}", dup );
                var nxt = dup.ofWhat.Match ( ch, ref dup.tail, new AbsPos ( pos ) );
                if ( nxt != null ) {
                    if ( Debug )
                        Console.WriteLine ( "in table {0}", dup );
                    // if match (has ch already) keep duplicate
                    dup.ofWhat = nxt;
                } else {
                    if ( Debug )
                        Console.WriteLine ( "diverged: {0} with {1}", dup, ch );
                    // if not match, then split table, create new case on ch, remove duplicate
                    dup.ofWhat.AddCase ( ch, dup.tail, new AbsPos ( pos ) );
                    duplicates.Remove ( dupNode );
                    dupPool.AddLast ( dupNode );
                }
                dupNode = dupNext;
            }

            /*
             * Create initial entry for ch, or record as duplicate
             */
            if ( rootEnt == null ) {
                stateTable [ ch - 'a' ] = new MatchRun ( new AbsPos ( pos ) );
            } else {
                Duplicate dup;
                if ( dupPool.Count > 1 ) {
                    dup = dupPool.First ();
                    dupPool.RemoveFirst ();
                    dup.SetDuplicate ( rootEnt, new RelPos ( 1 ), new AbsPos ( pos ) );
                }
                else 
                    dup = new Duplicate ( rootEnt, new RelPos  ( 1 ), new AbsPos ( pos ) );
                if ( Debug )
                    Console.WriteLine ( "adding duplicate on {0}: {1}", ch, dup ); 
                duplicates.AddLast ( dup );
            }

            pos++;
        }
        
        return cost;
    }
    
    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine());

        for (int tItr = 0; tItr < t; tItr++) {
            string[] nab = Console.ReadLine().Split(' ');

            int n = Convert.ToInt32(nab[0]);

            int a = Convert.ToInt32(nab[1]);

            int b = Convert.ToInt32(nab[2]);

            string s = Console.ReadLine();

            int result = buildString(a, b, s);
            
            textWriter.WriteLine ( "{0}", result );
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Build a String Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int t=0;t<T;t++){
            int N = sc.nextInt();
            int A = sc.nextInt();
            int B = sc.nextInt();
            String S = sc.next();
            System.out.println( buildStringCost(N,A,B,S) );
        }
    }
    
    public static int buildStringCost(int N, int A, int B, String S){
        int[] dp = new int[N];
        dp[0] = A;
        int lastL = 0;
        for(int k=1;k<N;++k){
            dp[k] = dp[k-1]+A;
            int L = lastL+1;
            while(L>0){
                String cur = S.substring(k-L+1, k+1);
                int idx = S.substring(0, k-L+1).indexOf(cur);
                if( -1==idx )
                    L--;
                else{
                    dp[k] = Math.min(dp[k], dp[k-L]+B);
                    break;
                }
            }
            lastL = L;
        }
        return dp[N-1];
    }
}

Build a String JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the buildString function below.
 */
function maxSub(s, r, m) {
    let i = m;
    while (i <= r.length) {
        if (s.indexOf(r.substr(0, i)) == -1)
            return i - 1;
        i++;
    }
    return i - 1;
}
function buildString(a, b, s) {
    /*
     * Write your code here.
     */
    let cost = [],
        s1 = s.split(''),
        state = [],
        max = 0;
    cost[s.length - 1] = 0;
    s1.map((x, i) => {
        let sub = s.substr(0, i + 1),
            rem = s.substr(i + 1);
        max = maxSub(sub, rem, max);
        state[i] = max;

})
for (let i = s.length - 2; i >= 0; i--) {
    let min = a + cost[i + 1];
    for (let j = 1; j <= state[i]; j++) {
        let c = b + cost[i + j];
        min = Math.min(min, c);
    }
    cost[i] = min;
}
return cost[0] + a;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const nab = readLine().split(' ');

        const n = parseInt(nab[0], 10);

        const a = parseInt(nab[1], 10);

        const b = parseInt(nab[2], 10);

        const s = readLine();

        let result = buildString(a, b, s);

        ws.write(result + "\n");
    }

    ws.end();
}

Build a String Python Solution

#!/bin/python3

import os
import sys
import re

#
# Complete the buildString function below.
#

def buildString(a, b, s):
    N = len(s)

    cost = [0]*N

    cost[0] = a
    index = 1
    for i in range(1,N):
        if s[index:i+1] not in s[:index] or index == -1:
            index = findLongestOccurence(s[:i+1], i)
        if index==-1:
            cost[i] = cost[i-1] + a
        else:
            cost[i] = min(cost[i-1]+a, cost[index-1]+b)
    return cost[-1]

def findLongestOccurence(s, index):
    indexHasChanged = False
    while s[index:] in s[:index]:
        index -= 1
        indexHasChanged = True
    return -1 if not indexHasChanged else index + 1



if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        nab = input().split()

        n = int(nab[0])

        a = int(nab[1])

        b = int(nab[2])

        s = input()
        
        result =  buildString(a, b, s)

        fptr.write(str(result) + '\n')

    fptr.close()