Binary search the optimal value when only latin and spaces. You don't have to iterate through all m. Calculate transition for n in O(1) time. Overall complexity should be something like O(|s|log(m)).