We propose frequency-domain interleaver for discrete Fourier transform spread orthogonal division multiplexing (DFT-s-OFDM) based on a linear- or quadratic permutation polynomial (LPP/QPP). Interleaving the Fourier coefficients (i.e., the DFT precoder output) implies that the modulation symbols become transmitted over both time- and frequency domain, which is beneficial over time-frequency selective channels. Despite that the single-carrier property is lost due to the interleaving, the peak-to-average-power ratio (PAPR) can be improved. The results show that a QPP can suppress the error floor of the bit/block error rate (BER/BLER) which occurs on channels with large Doppler spread and simultaneously reduce the PAPR. An LPP primarily decreases the PAPR, especially for BPSK, where the gain is several dB. We derive criteria of how to analytically determine the QPPs and the LPPs.