/*
VIM: let b:cf5build="clang++ -std=c++20 -O2 -pthread -I. {SRC} -o {OUT}"
VIM: let b:cf5run="{OUT}"
*/
#include <iostream>
#include <exception>
#include <chrono>
#include <string>
#include <string_view>
#include <unordered_set>
#include <vector>

/*
## Problem Description

  Given an input of a dictionary of words and an input string that does not
  contain spaces, write a method that returns a string with spaces inserted
  accordingly.

## Expected Completion Time

  For unoptimized recursive solution: 25 minutes

## Problem Complexity Level

  Coding Fluency: Medium

  Problem Solving: Medium

## Questions the candidate might ask

  1) Do you need to find all combinations of sentences?  Always return
    the sentence with the shorter valid matches.
  2) What if there are spaces already in the string?  Assume there aren't
    already spaces.
  3) What are the valid set of characters (eg. uppercase, symbols)?  Assume
    dictionary is always all lowercase and are letters.
  4) What happens if nothing matches in the dictionary?  Return null/none.
  5) What if there are left over characters in the string?  Return null/none.

## Sample inputs - Expected outputs

  Input: "bloombergisfun", ["bloom","bloomberg","is","fun"]
  Output: "bloomberg is fun"

## Input corner cases

  Input: "bloombergisfun", ["bloom", "bloomberg","is"]
  Output: None/Null

  Input: "bloombergisfun", ["bloom", "berg", "bloomberg","is","fun"]
  Output: "bloom berg is fun"

## Runtime complexity

Recursive Solution: O(2^N)
This solution O(N*K) where `K` is max length of word in vocab)

Note:
    hashing of a string is not an O(1) function, but O(N) therefore complexity
    is O(N*K^2). But it can be made O(N*K).

*/

using dict_t = std::unordered_set<std::string>;

std::string solution(const std::string& str, const dict_t& dict)
{
    size_t minw = str.size() +1;
    size_t maxw = 0;
    for (const auto& w : dict){
        minw = std::min(minw, w.size());
        maxw = std::max(maxw, w.size());
    }

    std::vector<std::string> memo(str.size()+1, std::string());

    for (size_t i = 0; i < str.size(); ++i){
        if (i != 0 && memo[i].empty()){
            continue;
        }
        for (size_t j = minw; j <= maxw && i+j <= str.size(); ++j){
            std::string candidate(str.data()+i, j);
            auto it = dict.find(candidate);
            if (it != dict.end()){
                memo[i+j]=memo[i] + " " + *it;
            }
        }
    }

    return memo[str.size()];
}

void test(const std::string& str, const dict_t& dict)
{
    std::cout << "dict=[";
    bool first = true;
    for (const auto& word : dict){
        if (first){
            first = false;
        } else {
            std::cout <<", ";
        }
        std::cout << word;
    }
    std::cout << "]\n";
    std::cout << "str='" << str << "' -> ";
    std::cout.flush();
    std::cout << "'" << solution(str, dict) << "'\n\n";
}

int main ( void )
{try{
    auto begin = std::chrono::high_resolution_clock::now();

    test("bloombergisfun", {"bloom","bloomberg","is","fun"});
    test("bloombergisfun", {"bloom","bloomberg","is"});
    test("bloombergisfun", {"bloom", "berg", "bloomberg","is","fun"});

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> seconds = end - begin;
    std::cout << "Time: " << seconds.count() << std::endl;
    return 0;
}
catch ( const std::exception& e )
{
    std::cerr << std::endl
            << "std::exception(\"" << e.what() << "\")." << std::endl;
    return 2;
}
catch ( ... )
{
    std::cerr  << std::endl
            << "unknown exception." << std::endl;
    return 1;
}}