Weighted Uniform String

See the original problem on HackerRank.

Solutions

A C++ solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
string s; cin >> s;
int q, i; cin >> q;
vector<int> w;
char last = 0;
for (auto c : s)
{
    if (c == last)
        w.push_back(w.back()+c-'a'+1);
    else
        w.push_back(c-'a'+1);
    last = c;
}
sort(begin(w), end(w));
while (q--)
{
    cin >> i;
    cout << (binary_search(begin(w), end(w), i) ? "Yes" : "No") << endl;
}

A C++ solution using std::set. Replace with std::unordered_set for \( O(1) \) lookup.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
string s; cin >> s;
int q, i; cin >> q;
set<int> w;

int last = 0;
int sum = 0;

for (auto c : s)
{
    int x = c-'a'+1;
    w.insert(x == last ? sum+x : x);
    sum = x == last ? sum+x : x;
    last = x;
}

while (q--)
{
    cin >> i;
    cout << (w.count(i) ? "Yes" : "No") << endl;
}

An Haskell solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import Data.List (sort)
import Data.Set (Set,member,fromList)

weight c = (fromEnum c) - (fromEnum 'a') + 1

-- Search q in the list
query :: Set Int -> Int -> Bool
query ws q = (member q ) ws

-- The list is optimized for searching
optimizeString :: String -> Set Int
optimizeString = fromList . sort . sumWeights . fmap weight

-- Map each number to the sum of previous equal numbers
-- e.g.: [1,2,3,3,4,4,4,5] -> [1,2,3,6,4,8,12,5]
sumWeights xs = ys where (_, _, ys) = foldl sumAdj (0, 0, []) xs

sumAdj (last, s, xs) x =
  if x == last
  then (x, s+x, s+x:xs)
  else (x,   x,   x:xs)

yesNo True = "Yes"
yesNo False = "No"

main = do
    contents <- getContents
    let (s:_:queries) = words contents
    let ws = optimizeString s
    putStrLn $ unlines $ yesNo <$> query ws <$> read <$> queries

A JavaScript one, using a regular expression to find the uniform substrings:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
'use strict';

// The actual solution
function weightedUniformStrings(s, queries) {
    const result = s.match(/([a-z])(\1)*/g);
    const values = result.flatMap((m) => Array.from(new Array(m.length),(val,index)=>(m.charCodeAt(0) - 97 + 1) * (index + 1)));
    return queries.map((q) => values.includes(q) ? 'Yes' : 'No')
}


// Boilerplate code
Array.prototype.flatMap = function(lambda) {
    return Array.prototype.concat.apply([], this.map(lambda));
};

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.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

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

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

    const s = readLine();

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

    let queries = [];

    for (let i = 0; i < queriesCount; i++) {
        const queriesItem = parseInt(readLine(), 10);
        queries.push(queriesItem);
    }

    let result = weightedUniformStrings(s, queries);

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

    ws.end();
}

A solution in C++ with a \( O(1) \) lookup complexity for each query (instead of \( O(\log U) \)):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
string s; cin >> s;
int q, i; cin >> q;

map<char, int> weights;

char last = 0;
int count = 1;
s += '\0';
for (auto c : s)
{
    if (c == last) {
        ++count;
    } else if (last != 0) {
        weights[last-'a'+1] = max(weights[last-'a'+1], count * (last-'a'+1));
        count = 1;
    }
    last = c;
}

for (auto cw : weights) {
    cerr << int(cw.first) << " " << cw.second << "\n";
}

while (q--)
{
    cin >> i;

    bool found = false;
    for (auto cw : weights) {
        if (cw.second >= i && (i % cw.first == 0))
            found = true;
    }

    cout << (found ? "Yes" : "No") << endl;
}

A “lazy” C++ solution where all possible substring are not determined before it is really needed.

If max weight is 26 and max length of s is 100000, then the max substring weight is 2’600’000.

I already know that if query is greater than 2’600’000, it undoubtedly doesn’t match any substring.

A table of 2’600’000 booleans is enough to store all possible substrings.

We do not evaluate all possible substring before starting querying, but we search for new matches only when the query doesn’t match any value already in the table.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
std::string s;
int n;
std::cin >> s;
std::cin >> n;

/* Constraints:
 * w is at most 26
 * s length is at most 100'000
 * -> at most 2600000 possible substrings
 */
static constexpr int maxSubstrNum = 26 * 10e5;

bool table[maxSubstrNum];
auto it = s.begin();
int last = 0;
int lastSum = 0;

/* Lazy evaluation of string character */
auto tryNext = [&](){
    if (it == s.end()) return false;

    int w = *it - 'a' + 1;

    if (w == last) {
        lastSum += w;
    } else {
        last = w;
        lastSum = w;
    }

    table[lastSum] = true;

    ++it;
    return true;
};

while (n--) {
    int x;
    std::cin >> x;

    /* If x is greater than 2600000, we already know it
     * cannot match without searching.
     * Evaluate next character in string only if we cannot find
     * any match in the already evaluated substrings.
     */
    while (x < maxSubstrNum && !table[x] && tryNext()); /* empty while body */

    /* At this point: match is found or all the substrings have been evaluated
     * without finding any match. */
    std::cout << (x < maxSubstrNum && table[x] ? "Yes\n" : "No\n");
}
We've worked on this challenge in these gyms: modena  milan  padua  barcelona  turin 
comments powered by Disqus