# 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 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 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; } 

  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 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 52 53 54 55 56 57 58  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; /* * Please note that the default stack size on MSVC is 1 MB so allocating an * array of 2600000 bools will result in a stack overflow. * To workaround this issue you may use one of those: * - std::vector table(maxSubstrNum,0) * - std::vector table(26*s.size(),0) */ 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