To answer your question you need the so called invariant factors e.g. https://www2.bc.edu/~reederma/LinAlgAdv.pdf but there are lot of material on line.
The invariant factors of $A \in \mathbb{K}^{n,n}$are monic polynomials $f_1,f_2,\cdots,f_n$ such that $f_{i} | f_{i+1}$, $f_n$ is the minimal polynomial of $A$ and the product $f_1 \cdots f_n = \pm \chi_A$ is the characteristic polynomial of $A$. Each conjugation class of matrices in $\mathbb{K}^{n,n}$ is determined by the sequence $f_1,\cdots,f_n$ and reciprocally, any sequence of monic polynomials $f_1,\cdots,f_n$ such that $f_{i} | f_{i+1}$ and the product $f_1 \cdots f_n$ has degree $n$ gives a conjugation class.
From now assume that $K$ is an algebraically closed field and assume that $f$ and $g$ are as in the OP. Split $f = \prod_i (x-\lambda_i)^{m_i}$ where $\lambda_i \neq \lambda_j$ for $i \neq j$. Then $g = \prod_i (x-\lambda_i)^{c_i} $ with $1 \leq m_i \leq c_i$ and $\sum_j c_j = n$. If we want that $f$ and $g$ determine the conjugation class then the numbers $m_i, c_i$ $i=1,\cdots,k$ must determine the sequence $f_1,\cdots,f_n$ of invariant factor. To be so for each $i=1,\cdots,k$ the two numbers $m_i,c_i$ must determine the exponent $0 \leq r_{ij}$ of $(x-\lambda_i)$ of the invariant factor $f_j$. By the divisibility property we know that $r_{ij} \leq r_{i (j+1)}$. So at this point we have a combinatorial problem. Namely, we have a $k \times n$ matrix $F$ with non negative integers $r_{ij}$ such that
1)the sequence is incresing on each row i.e. $r_{ij} \leq r_{i (j+1)}$,
2)we know the last column of $F$ (i.e. we know the decomposition of the minimal polynomial hence $r_{i n} = m_i$),
3)we know the sum $c_i$ of each row of $F$ (since the product $f_1 \cdots f_n$ is $g$ ).
The question is which are the conditions on the last column and the $c_i$ to determine univocally the whole $k \times n$ matrix ?
If I am not wrong the condition is that for each $i$ one of the following holds:
(i) $m_i = 1$
(ii) $m_i = c_i$
(iii) $m_i + 1 = c_i$
So the two polynomials $f,g$ are the minimal and the characteristic polynomial of a (unique up to conjugation) matrix $A \in \mathbb{K}^{n,n}$ if and only if :
1) $f = \prod_i (x-\lambda_i)^{m_i}$ where $\lambda_i \neq \lambda_j$ for $i \neq j$ and $g = \prod_i (x-\lambda_i)^{c_i} $ with $1 \leq m_i \leq c_i$ and for each $i$ the numbers $m_i,c_i$ satisfies one of the three conditions (i), (ii) or (iii) above.
If $\mathbb{K}$ is not algebraically closed then you can replace the polynomials $(x - \lambda_i)$ by monic irreducible polynomials $p_i \in \mathbb{K}[x]$ and obtain a similar result. Namely, $f = \prod_i p_i^{m_i}$ where $p_i \neq p_j$ for $i \neq j$ and $g = \prod_i p_i^{c_i}$, now you need that $\sum_i c_i \deg(p_i) = n$ but the conditions on $m_i, c_i$ are the same as for $\mathbb{K}$ algebraically closed.
