medium
1 views

Longest String – Diagonally

Find the longest string formed by traversing diagonally from a given cell in a matrix

Understand the Problem

Problem Statement

Problem Description

Given a character matrix of size R×C and a position (X, Y), form four string values by traversing diagonally from the given cell in four directions:

  • S1: Traverse diagonally in the top-left direction
  • S2: Traverse diagonally in the top-right direction
  • S3: Traverse diagonally in the bottom-right direction
  • S4: Traverse diagonally in the bottom-left direction

Finally, print the longest string among these four string values. If two or more string values have the same maximum length, print the first occurring string.

Constraints

Constraints

  • 2 ≤ R, C ≤ 50
  • 1 ≤ X ≤ R
  • 1 ≤ Y ≤ C
  • All matrix elements are single characters
  • Position coordinates are 1-indexed in input, must be converted to 0-indexed

Examples

Example 1
Input
6 8
D y j w h r y t
s a r A v g t y
l E b v m B y F
F p z w E j n s
m f p D j d r y
D v w r s e m D
4 5
Output
Evry
Explanation

From position (4,5) (0-indexed: 3,4): - S1 (top-left): Evry (length 4) - S2 (top-right): EBtt (length 4) - S3 (bottom-right): Edm (length 3) - S4 (bottom-left): EDw (length 3) Both S1 and S2 have maximum length 4, but S1 occurs first, so 'Evry' is printed.

Example 2
Input
10 7
E x e k e B h
e c j D b y e
j b l b t b d
h h C C h s d
D q j h d s d
n z s k D n h
l p i x k E D
b e a n b d v
b y d j y d d
t r y F u n u
8 2
Output
eikdsd
Explanation

From position (8,2) (0-indexed: 7,1), the longest diagonal string is 'eikdsd' formed by traversing in one of the diagonal directions.

Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* function(int row, int col, char arr[row][col], int var1P, int var2P, int var1, int var2) {
    char* temp = malloc(row * col * sizeof(char));
    int ind = 0;
    while (var1P >= 0 && var1P < row && var2P >= 0 && var2P < col) {
        temp[ind++] = arr[var1P][var2P];
        var1P += var1;
        var2P += var2;
    }
    temp[ind] = '\0';
    return temp;
}

int main() {
    int row, col;
    scanf("%d %d", &row, &col);
    char arr[row][col];
    for (int ele = 0; ele < row; ++ele) {
        for (int j = 0; j < col; ++j) {
            scanf(" %c", &arr[ele][j]);
        }
    }
    int Positioni, PositionJ;
    scanf("%d %d", &Positioni, &PositionJ);
    Positioni--;
    PositionJ--;
    
    char* answer;
    char* arr1 = function(row, col, arr, Positioni, PositionJ, -1, -1);
    char* arr2 = function(row, col, arr, Positioni, PositionJ, -1, 1);
    char* arr3 = function(row, col, arr, Positioni, PositionJ, 1, 1);
    char* arr4 = function(row, col, arr, Positioni, PositionJ, 1, -1);
    
    int l1 = strlen(arr1), l2 = strlen(arr2), l3 = strlen(arr3), l4 = strlen(arr4);
    if (l1 >= l2 && l1 >= l3 && l1 >= l4) {
        answer = arr1;
    } else if (l2 >= l1 && l2 >= l3 && l2 >= l4) {
        answer = arr2;
    } else if (l3 >= l1 && l3 >= l2 && l3 >= l4) {
        answer = arr3;
    } else {
        answer = arr4;
    }
    printf("%s", answer);
    
    free(arr1);
    free(arr2);
    free(arr3);
    free(arr4);
    return 0;
}
Time:O(R + C) - Each diagonal traversal takes at most O(min(R,C)) time, and we do 4 traversals
Space:O(R + C) - We store up to 4 strings, each of maximum length min(R,C)
Approach:

The C solution:

  1. Defines a function that traverses the matrix in a specified diagonal direction
  2. Uses dynamic memory allocation to store each diagonal string
  3. Traverses until matrix boundaries are reached
  4. Compares string lengths using conditional statements
  5. Prints the longest string and frees allocated memory

Key points: Uses 0-indexed array access, manual memory management, and careful boundary checking.

Visual Explanation

Loading diagram...
All Problems