Step 1. For an arbitrary set of strings $\{x_i\}$, first sort them by their length. Then the kernel matrix is block-diagonal, since the kernel value between any two strings of different lengths is zero.
This lets us see that we only need to consider strings of the same length; how?
Step 2. So, we only need to consider a set of strings $\{ x_i \}$ all of length $m$. Then we can see that $$K(x, z) = \frac1m \sum_{i=1}^m \mathbb{1}(x_i = z_i), \tag{*}$$
where $\mathbb{1}(x_i = z_i)$ is 1 if $x_i = z_i$, 0 otherwise.
Looking at it this way lets us find an explicit feature map from the space of strings of length $m$ to vectors of a certain length: that is, $K(x, z) = \varphi(x)^T \varphi(z)$, for some function $\varphi$. Do you see what that function is?
Hint: if $a = (0, 1, 0, 1)$ and $b = (1, 1, 0, 0)$, then $a^T b = 0 + 1 + 0 + 0$; in general, for length-$k$ vectors whose entries are all either $0$ or $1$, $a^T b = \sum_{i=1}^k a_i b_i = \sum_{i=1}^k \mathbb 1(a_i = 1, b_i = 1)$. So you might want to come up with some function $\varphi$ that turns this into something that looks like (*).
Step 3. From there, it's a standard result that we have positive definiteness pretty quickly. Supposing that $\varphi$ maps into $\mathbb R^k$, let $\Phi$ be the $n \times k$ matrix whose $i$th row is $\varphi(x_i)$, so that $(\Phi \Phi^T)_{ij} = \varphi(x_i)^T \varphi(x_j) = K(x_i, x_j)$. Then the psd condition is that for all $a \in \mathbb R^n$, we have that
$$
\sum_{i=1}^n a_i K(x_i, x_j) a_j = a^T K a = a^T \Phi \Phi^T a = (\Phi^T a)^T (\Phi^T a) = \lVert \Phi^T a \rVert^2 \ge 0
.$$
Best Answer
Yes, it is. The proof is as follows,
$$K(x, y) = \min(f(x)g(y), f(y)g(x))=\min(\frac{f(x)}{g(x)}, \frac{f(y)}{g(y)})g(x)g(y)$$ $$\min(\frac{f(x)}{g(x)}, \frac{f(y)}{g(y)})=\int\mathbb{1}_{[0, \frac{f(x)}{g(x)}]} \mathbb{1}_{[0, \frac{f(y)}{g(y)}]} = \langle \mathbb{1}_{[0, \frac{f(x)}{g(x)}]}, \mathbb{1}_{[0, \frac{f(y)}{g(y)}]} \rangle = \langle \phi(x), \phi(y) \rangle$$
By Aronszajn theorem using $\phi(x) = \mathbb{1}_{[0, \frac{f(x)}{g(x)}]}$ , $\min(\frac{f(x)}{g(x)}, \frac{f(y)}{g(y)})$ is positive definite kernel.
$g(x)g(y)$ is trivially a positive kernel as it is a product.
$K(x, y)$ is thus the product of two positive definite kernels, so it is a positive definite kernel.