#include <algorithm>
#include <cctype>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
/**
* Converts a word to a normalized form:
* - lowercase
* - punctuation removed
*/
std::string NormalizeWord(const std::string& word)
{
std::string result;
for (char ch : word)
{
if (std::isalnum(static_cast<unsigned char>(ch)))
{
result += static_cast<char>(
std::tolower(static_cast<unsigned char>(ch)));
}
}
return result;
}
/**
* Tokenizes text into normalized words.
*/
std::vector<std::string> Tokenize(const std::string& text)
{
std::vector<std::string> words;
std::istringstream stream(text);
std::string token;
while (stream >> token)
{
std::string normalized = NormalizeWord(token);
if (!normalized.empty()) {
words.push_back(normalized);
}
}
return words;
}
/**
* Finds the smallest window containing all target words.
*
* Time Complexity: O(n)
* Space Complexity: O(k)
*
* where:
* n = number of words in the text
* k = number of target words
*/
std::string FindDensestSection(
const std::string& text,
const std::vector<std::string>& targetWords)
{
const std::vector<std::string> words = Tokenize(text);
if (words.empty() || targetWords.empty()) {
return {};
}
std::unordered_set<std::string> targets;
for (const auto& word : targetWords) {
targets.insert(NormalizeWord(word));
}
std::unordered_map<std::string, int> windowCounts;
std::size_t left = 0;
int matchedWords = 0;
std::size_t bestStart = 0;
std::size_t bestLength =
std::numeric_limits<std::size_t>::max();
for (std::size_t right = 0; right < words.size(); ++right)
{
const std::string& currentWord = words[right];
if (targets.contains(currentWord)) {
if (++windowCounts[currentWord] == 1) {
++matchedWords;
}
}
while (matchedWords ==
static_cast<int>(targets.size()))
{
std::size_t currentLength =
right - left + 1;
if (currentLength < bestLength) {
bestLength = currentLength;
bestStart = left;
}
const std::string& leftWord = words[left];
if (targets.contains(leftWord)) {
if (--windowCounts[leftWord] == 0)
{
--matchedWords;
}
}
++left;
}
}
if (bestLength ==
std::numeric_limits<std::size_t>::max())
{
return {};
}
std::ostringstream result;
for (std::size_t i = bestStart;
i < bestStart + bestLength;
++i)
{
if (i > bestStart) {
result << ' ';
}
result << words[i];
}
return result.str();
}
int main()
{
const std::string text =
"A small research team gathered in a quiet office "
"to discuss a new software project. "
"The team reviewed several design proposals and "
"compared their advantages. "
"One engineer suggested building a simple prototype "
"before committing to a larger effort. "
"The prototype design revealed a few performance issues. "
"After several days of testing, the team identified "
"the root cause of the slowdown. "
"The engineers improved the design and measured "
"significantly better results. "
"The project moved forward with greater confidence.";
const std::vector<std::string> targetWords =
{
"team",
"prototype",
"design"
};
const std::string result =
FindDensestSection(text, targetWords);
std::cout << "Densest section:\n\n"
<< result << '\n';
}
/*
run:
Densest section:
prototype design revealed a few performance issues after several days of testing the team
*/
