Lexicographically minimal grid path algorithm

I'm trying to solve the following problem: Minimal Grid Path (CSES). Here is the content of the problem:

You are given an n x n grid whose each square contains a letter. You should move from the upper-left square to the lower-right square. You can only move right or down. What is the lexicographically minimal string you can construct?

Input: The first line has an integer n: the size of the grid. After this, there are n lines that describe the grid. Each line has n letters between A and Z.

Output: Print the lexicographically minimal string.

Constraints: 1 <= n <= 3000

I am currently attempting to use dynamic programming to solve the problem. Here is the code:

#include <bits/stdc++.h>

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >>n;

  vector<string> prev;
  string s;
  cin >> s;
  prev.push_back(s.substr(0, 1));
  for (int j=1; j<n; j++) { // first row
    prev.push_back(prev.back()+s[j]);
  }

  for (int i=1; i<n; i++) {
    string s;
    cin >> s;
    prev[0] += s[0];
    for (int j=1; j<n; j++) {
      prev[j] = min(prev[j-1], prev[j]) + s[j];
    }
  }

  cout << prev.back() << '\n';
}

Basically, I'm going through the grid row by row, and for each cell in the row, I am keeping track of the lexicographically minimal string required to get to that cell. For every row after the first, I set the string at index j of prev to be the lexicographic minimum of the string at index j-1 and at index j in the row above the current row (which is actually prev[j] since prev[j] still represents the cell in the previous row at column j), plus the extra character at index j.

However, this solution is much too slow (the time limit is one second, and with certain test cases, this algorithm greatly exceeds the time limit. Submit this code to the CSES website to see the specific test cases). How can I make it faster?

It is possible to use string hashing and binary lifting to speed up your current solution, but there is a simpler method.

The minimal string can be built one character at a time, starting from the character at the top left corner.

To get each subsequent character, check the characters to the right and bottom of each of the possible positions of the previous character and eliminate duplicate positions. Then, take the minimum of the characters at all these positions and discard the positions that are not equal to that character for the next iteration.

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <ranges>

int main() {
    int n;
    std::cin >> n;
    std::vector<std::string> grid(n);
    for (auto& row : grid) std::cin >> row;
    std::vector<std::pair<int, int>> positions{{0, 0}};
    while (!positions.empty()) {
        positions.erase(std::ranges::unique(positions).begin(), positions.end());
        char minc = std::ranges::min(positions | std::views::transform([&](auto& p) { 
            return grid[p.first][p.second];
        }));
        std::cout << minc;
        decltype(positions) nextPositions;
        for (auto [r, c] : positions)
            if (grid[r][c] == minc) {
                if (r + 1 < n) nextPositions.emplace_back(r + 1, c);
                if (c + 1 < n) nextPositions.emplace_back(r, c + 1);
            }
        positions = std::move(nextPositions);
    }
}