Problem 2810 - Faulty Keeyboard

Simulate the keyboard behavior as described. When encuontering character 'i', reverse the current string.

class Solution {
public:
    string finalString(string input) {
        string result = "";
        
        for(char c : input) {
            if(c == 'i') {
                reverse(result.begin(), result.end());
            } else {
                result += c;
            }
        }
        
        return result;
    }
};

Problem 2811 - Check if Array Can Be Split

For arrays with length ≤ 2, splitting is always possible. For longer arrays, if any adjacent pair sums to at least m, we can remove elements one by one untill only that pair remains.

class Solution {
public:
    bool canSplitArray(vector<int>& arr, int threshold) {
        int size = arr.size();
        
        if(size <= 2) return true;
        
        for(int i = 1; i < size; i++) {
            if(arr[i] + arr[i-1] >= threshold) {
                return true;
            }
        }
        
        return false;
    }
};

Problem 2812 - Find the Safest Path

To avoid timeout on large datasets, precompute safety factors for each cell using multi-source BFS, then find the path with maximum safety factor using a priority queue.

class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> distances(n, vector<int>(n, -1));
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        queue<pair<int,int>> bfsQueue;
        
        // Directions: up, down, left, right
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        
        // Initialize queue with all thief positions
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j]) {
                    bfsQueue.push({i, j});
                    distances[i][j] = 0;
                }
            }
        }
        
        // Multi-source BFS to compute safety distances
        while(!bfsQueue.empty()) {
            auto [x, y] = bfsQueue.front();
            bfsQueue.pop();
            
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                if(nx >= 0 && ny >= 0 && nx < n && ny < n && distances[nx][ny] == -1) {
                    bfsQueue.push({nx, ny});
                    distances[nx][ny] = distances[x][y] + 1;
                }
            }
        }
        
        // Dijkstra's algorithm to find maximum safety path
        priority_queue<pair<int, pair<int,int>>> pq;
        pq.push({distances[0][0], {0, 0}});
        visited[0][0] = true;
        int minSafety = INT_MAX;
        
        while(!pq.empty()) {
            auto [safety, coords] = pq.top();
            auto [x, y] = coords;
            pq.pop();
            
            minSafety = min(safety, minSafety);
            
            if(x == n-1 && y == n-1) {
                return minSafety;
            }
            
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                
                if(nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                    pq.push({distances[nx][ny], {nx, ny}});
                    visited[nx][ny] = true;
                }
            }
        }
        
        return 0;
    }
};