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.

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()
Other Solutions