Lets denote the princesses by $P_1,P_2,\ldots, P_n$ and the frogs by $F_i$ such that the frog $F_i$ corresponds to the prince that the princess $P_i$ loves. If each princess can stand kissing at most $k$ frogs. Then we can save $k$ princes, to do so its enough for all the princesses to kiss the frogs $F_1,F_2,\ldots,F_k$. Lets prove we cant do better for $k<n$. Suppose we can assure to save $k+1$ princes. WLOG the princes loved by $P_1,P_2,\ldots, P_{k+1}$ are saved. Then $F_1,F_2,\ldots, F_{k}$ had to be kissed by all the princesses $P_{k+1},P_{k+2},\ldots P_{n}$, otherwise if frog $F_x, x\leq k$ was not kissed by a $P_y, y>k$, then wouldnt be possible to distinguish $F_x$ from $F_y$. Since each princess $P_y,y>k$ stand kissing at most $k$ frogs, then $F_{k+1}$ could not have been saved, which its a contradiction.

Luve96 wrote: ... Then $F_1,F_2,\ldots, F_{k}$ had to be kissed by all the princesses $P_{k+1},P_{k+2},\ldots P_{n}$, otherwise if frog $F_x, x\leq k$ was not kissed by a $P_y, y>k$, then wouldnt be possible to distinguish $F_x$ from $F_y$. I do not get it. Suppose no one among $P_{k+1},P_{k+2},\ldots P_{n}$ kissed the frog $F_x,$ for some $x\leq k$, but it was kissed by $P_x$ and turned back to a prince. Then what?

We will show that the maximum number of princes that can be saved is $\min(k,n)$. It is clear that $\min(k,n)$ princes can be saved if the princesses take $\min(k,n)$ frogs and each kisses all of them. Let us show that this is the maximum number. Look on it as on a game between the princesses and the witch. Assume the witch forgets about the correspondence prince - frog and she can turn any frog back into any prince she wishes. She wants to delay the right guesses of the princesses as long as possible. We represent the situation as a $(n,n)$ bipartite graph on the sets of vertices $A$ (the princesses) and $B$ (princes). So, we can connect, one by one, $a\in A$ to $b\in B$ - this means that $a$ kisses $b$. After that, the witch has two options: 1) to tell us that the last connected edge was a right correspondence princes and her prince. 2) to refute the edge as not being the right guess. Note that the witch can refute every next kiss (edge) as long as there is a full matching in the complementary graph $\overline{G}$ of $G$, which consists of all edges not in $E(G)$. Indeed, if after the last drawn edge, we can perfectly match each $a\in A$ to $b\in B$ such that $ab\not\in E$ then hypothetically this can be the right correspondence and no one can prove that the witch cheats. But if after placing an edge $ab$ we cannot match anymore the vertices of $\overline{G}$ then the witch is forced to admit that $ab$ is a pair of princess and her prince, because otherwise she will be caught blood handed. So, she does it. At this moment there is no perfect matching $A\to B$ in $\overline{G}$. Therefore, by Hall's condition, there is $A'\subset A$ and $B'\subset B$ such that $|N(A')|<|A'|$ (in $\overline{G}$). We denote $B':= N(A')$ (in $\overline{G}$). We would have a perfect matching in $\overline{G}$ if we add back the edge $ab$ to $\overline{G}$. This means that $|B'|=|A'|-1, a\in A', b\not\in B'$. This also means that all the vertices in $A'$ are connected to all the vertices in $B\setminus B'$ (in $G$). Let $A_1:=A'\setminus \{a\}, B_1:=B', A_2:=A\setminus A', B_2:=B\setminus (B'\cup\{b\})$. Now, each vertex $a_1$ in $A_1$ is connected to $b$ and to all the vertices in $B_2$ (in $G$), thus it has degree at least $|B_2|+1$. This is the number of kisses the princess $a_1$ has exhausted for nothing - her lover is not there. We delete those edges. We are left with two bipartite graphs $G_1(A_1,B_1), G_2(A_2,B_2)$ with $|A_1|=|B_1|,|A_2|=|B_2|$. In both of them there is a perfect matching in the complementary graphs $\overline{G_1}, \overline{G_2}$. Each princess in $A_1$ is allowed to make altogether no more than $k-|B_2|-1$ kisses to princes in $B_1$ (some of them are possibly made). The witch can be even generous to the princesses in $A_2$ - she allows them again $k$ possible kisses. Observe that the real matching: prince - princess is between $A_1, B_1$ and $A_2, B_2$. Now we have one revealed pair $ab$ and two graphs $G_1$ (it is empty) and $G_2$. The number of edges allowed to be drawn from each $a_1\in A_1$ is $k-|B_2|-1$. Now, the witch continues recursively the same procedure in each of the graphs: $G_1$ and $G_2$. The maximum number of princes that can be saved in $G_1$ is $\min(|A_1|, k-|A_2|-1)\le k-|A_2|-1$, and in $G_2$ - it is $min(|A_2|,k)=|A_2|$. Hence, the maximum number of the saved princes in both graphs is at most $k-1$. Adding the edge $ab$ (the prince $b$ is saved), we get that complying to that strategy, the witch will save no more than $k$ princes.

Answer is $min(k,n)$ Let the the sets $A_1, A_2, ..., A_n$ represent the princesses that kissed each frog. Thus, if $a \in A_i$, then princess $a$ kissed frog $I$. We will let the princesses kiss the frogs until one of the frogs turn back into a prince. As the previous answer mentioned, we can view it as a game where the witch tries to delay the right guesses as long as possible while still making sure that each frog is corresponded to a unique prince. Thus, the princesses must know which prince corresponds to the frog one move before the first frog turns into a prince. WLOG let frog $I$ correspond to prince $i$. Let us also WLOG assume that frog 1 was the first frog that turned into a prince. Let us analyse the state of the game one move before frog 1 turns into a prince. Let $X$ be the set of frogs such that $1 \notin A_i, i \in X$. Claim: There must exist a set of frogs $F$ such that 1. $A_i = A_1 \cup \{1\}$ for $i \in F$ 2. $|F| = n - |A_i|$ for $i \in F$ (These set of rules basically partitions the frogs into 2 sets where one set of frogs can only correspond to prince $i$ where $i = 1$ or $i \in A_1$, and of those set of frogs, only one of them was not kissed by princess 1, therefore that frog is forced to correspond to prince 1.) Proof: We will assume the above is not true. Let us have a graph where there is a directed edge from $a$ to $b$ iff $a \notin A_b$. Notice that if there exists a cycle, then the witch is able to shift the frogs in the cycle. (e.g. if $1 \to 2 \to 3 \to 1$ then we can shift the frogs such that prince 1 corresponds to frog 2, prince 2 corresponds to frog 3, etc.) let $Y = X' \setminus \{1\}$. If $i \in Y$ and $i \notin A_1$, then we have a cycle of length 2 where $i \to 1, 1\to i$ and thus we can make frog 1 correspond to frog i, which is a contradiction. Thus, $Y \in A_1$ and thus $|A_1| > n - |X| + 1$. Now we will define a set $Z = A_1'$ and $W = A_1$. It is obvious that there is a directed path from each number in Z to 1. There must exist a directed edge from $a \in W$ to $b \in Z$, otherwise every number $i$ in $Z$ will have the property $W \subseteq A_i$ and $|Z| = n - |W|$ thus $F$ can be $|Z| \setminus \{1\}$ and the claim is then true, making a contradiction. Also, note that if $1 \notin A_a$, then there is a cycle $b \to 1 \to a \to b$ and thus we can shift the numbers to make frog 1 correspond to prince not 1, creating a contradiction. This means $1 \in A_a$. We can add $a$ to $Z$ and remove $a$ from $W$. Note that all the numbers in $Z$ still have a path towards 1, all numbers $i \in Z$ have the property $1 \in A_i$ and $W \subseteq A_1$. This allows us to repeat the process above until there are no numbers $i$ in $W$ s.t. $1 \in A_i$. But then if we repeat the process again, then we are forced to have a set F that satisfies the properties since no numbers $i$ in $W$ s.t. $1 \in A_i$. $\Box$ Now let $C = A_1$. Note that we have used up at least $n - |C|$ kisses for each princess $i \in C$ and we know there are only $|C|$ frogs left that can correspond to a prince in $C$. But now this is the same problem as the original, but now $n := |C|, k := k - n + |C|$. Since $k$ and $n$ decreases, we can have an induction argument to show that $|C| - (k - n + |C|) = n - k$ frogs will never be able to turn into a prince. Note the base case is trivial as we have only 1 princess and 1 frog, gurarnteeing the answer to be 1. Thus, the upper bound is k. The lower bound can be obtained by each princess kissing the same $k$ frogs.