Sampling of subsets with repeat
Let $l$ be the number of distinct characters in the input string. So our input size is summarized by $n, k, l$, with $k \le n$ and $l \le n$.

Here is one efficient way to do it. In the first step, since the order of characters in the string doesn't matter, let's turn it into a map:
$$
M = \{a \mapsto 1, d \mapsto 3, y \mapsto 1\}.
$$
The idea of our algorithm is to first calculate the number of possible permutations of $k$ elements from $M$, and then to use this to generate one randomly.

Step 1: calculating the number of possible permutations

We use dynamic programming. We actually calculate, more generally, the quantity
$$
p[i,j] \qquad \text{ for } 0 \le i \le k \text{ and } 0 \le j \le l,
$$
which represent the *number of permutations of length $i$, which use only the first $j$ elements of the map. For example, in the example problem (input "daddy", $k = 2$), we have
\begin{align*}
p[0, 0] &amp;= p[0, 1] = p[0, 2] = p[0, 3] = 1 \quad \text{(empty string)} \\
p[1, 1] &amp;= 1 \quad \text{(strings of length 1 using only a -- so just "a")} \\
p[1, 2] &amp;= 2 \quad \text{(strings of length 1 using a and d -- so "a" and "d")} \\
p[1, 3] &amp;= 3 \quad \text{("a", "d", and "y")} \\
p[2, 1] &amp;= 0 \quad \text{(no strings of length two using only a since only one a is allowed)} \\
p[2, 2] &amp;= 3 \quad \text{("ad", "da", and "dd")} \\
p[2, 3] &amp;= 7 \quad \text{("ad", "da", "dd", "ay", "ya", "dy", "yd")}
\end{align*}

Now how do we calculate $p$? We can use a recursive algorithm. Let $M[j]$ denote the value of $M$ on the $j$th character (so in our example, $M[1] = 1, M[2] = 3, M[3] = 1$). Then
$$
p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1].
$$

What this formula says is: pick $i'$ places to put character $j$. For example, in our running example for $p[2, 3]$, it says pick $i'$ places to put the character $y$ in a string of length $2$. Then for the remaining $i- i'$ places, we fill them in with a string only using the first $j-1$ characters (which can be done in $p[i-i', j-1]$ ways). The variable $i'$ ranges from $0$ to $M[j]$ because we can only use character $j$ at most $M[j]$ times.

This recurrence allows us to calculate the entire table of $p[i,j]$ in approximately $O(nk)$ time.

Step 2: Picking a permutation at random

The total number of permutations is $p[k, l]$. So pick a random number $r$ from $1$ to $p[k, l]$.

Now recall the recurrence relation 
$$
p[i, j] = \sum_{i' = 0}^{M[j]} \binom{i}{i'} p[i - i', j-1].
$$

Very roughly, we can use this recurrence relation to enumerate the $r$th permutation.
To evaluate the $r$th permutation of $p[i,j]$ total, evaluate the above sum and locate the term where the $r$th permutation would fall. For example if $r = 4$ and there are $7$ total permutations, and the sum gives you $3 + 4$, then $4$ falls fourth out of $7$, so it falls in the second group. Then, we are looking for the first out of $4$ permutations in the second group, which we can recursively find by picking a random permutation from $p[i - i', j-1]$.