returning a "variable string literal" from a function

returning a "variable string literal" from a function

I have some function that needs to return a const char* (so that a whole
host of other functions can end up using it).
I know that if I had something defined as follows:
const char* Foo(int n)
{
// Some code
.
.
.
return "string literal, say";
}
then there is no problem. However am I correct in saying that if Foo has
to return some string that can only be determined at runtime (depending on
the parameter n, (where each n taking any value in [0, 2^31-1] uniquely
determines a return string)) then I have to use the heap (or return
objects like std::string which use the heap internally)?
std::string seems too heavyweight for what I want to accomplish (at least
two functions will have to pass the parcel), and allocating memory inside
Foo to be freed by the caller doesn't strike me as a safe way of going
forward. I cannot (easily) pass in references to the objects that need
this function, and not that I believe it is possible anyway but macro
trickery is out of the question.
Is there something simple that I have not yet considered?