DELROW (HSGHN L9 2020-2021)

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

constexpr int N = 5e3 + 5;
string s[N];
int m, n, id[N], p[N], cnt[N];

void Read()
{
    cin >> m >> n;

    for (int i = 1; i <= m; ++i)
    {
        string v;
        cin >> v;

        for (int j = 0; j < n; ++j)
            s[j + 1].push_back(v[j]);
    }
}

// Counting Sort
void Sort()
{
    for (int i = m - 1; ~i; --i)
    {
        for (int j = 0; j < 26; ++j)
            cnt[j] = 0;

        for (int j = 1; j <= n; ++j)
            ++cnt[s[id[j]][i] - 'a'];

        for (int j = 1; j < 26; ++j)
            cnt[j] += cnt[j - 1];

        for (int j = n; j; --j)
            p[cnt[s[id[j]][i] - 'a']--] = id[j];

        swap(id, p);
    }
    for (int i = 1; i <= n; ++i)
        p[id[i]] = i;

    for (int i = 1; i <= n; ++i)
        while (p[i] != i)
        {
            swap(s[p[i]], s[i]);
            swap(p[p[i]], p[i]);
        }
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
    {
        reverse(s[i].begin(), s[i].end());
        id[i] = i;
    }

    /// O(n * m) sort
    Sort();
    /// O(n * m * log(m)) sort
    // sort(s + 1, s + n + 1);

    int ans(m);

    for (int i = 1; i < n; ++i)
    {
        int j = 0;
        while (j < m && s[i][j] == s[i + 1][j])
            ++j;
        ans = min(ans, m - j - 1);
    }

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("DELROW.INP", "r", stdin);
    freopen("DELROW.OUT", "w", stdout);

    Read();
    Solve();
}