Given an array arr[] of strings of same length, the task is to count the number of columns to be deleted so that all the rows are lexicographically sorted.
Examples:
Input: arr[] = {“hello”, “neveropen”}
Output: 1 Deleting column 1 (index 0) Now both strings are sorted in lexicographical order i.e. “ello” and “eeks”.Input: arr[] = {“xyz”, “lmn”, “pqr”}
Output: 0 All rows are already sorted lexicographically.
Approach 1:
Convert the given Vector/array of string into a char grid of n*m as n will be the number of row (number of string in vector/array) and m will be there size of string/length.then we will formally traverse over all the row and column and check for sorted or not if they are then continue. if they are not then we will save its column number and at the end we will return number of column that need to remove in order to make all the rows lexicographically sorted.
C++
#include <bits/stdc++.h>#define int long longusing namespace std;int n, m;bool test(int i, int j, vector<vector<char> >& v){ vector<char> x; for (int k = j; k < m; k++) { x.push_back(v[i][k]); } if (is_sorted(x.begin(), x.end())) { return 1; } return 0;}void solve(vector<string>& strs){ // std::cout << "/* message */" << '\n'; n = strs.size(); m = strs[0].size(); vector<vector<char> > v(n, vector<char>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (auto it : strs[i]) v[i][j++] = it; } } // for(auto it:v){ // for(auto vt:it)cout<<vt<<" "; // cout<<endl; // } int res = 0; for (int i = 0; i < n; i++) { int cnt = res; if (is_sorted(v[i].begin(), v[i].end())) { ++cnt; continue; } for (int j = cnt; j < m; j++) { if (test(i, j, v)) { break; } else ++cnt; } res = cnt; } cout << res << endl;}// Driver Codesigned main(){ vector<string> v{ "hello", "neveropen" }; vector<string> x{ "xyz", "lmn", "pqr" }; // cout<<solve(v)<<endl; solve(v); solve(x);} |
Java
// Java code for the above approachimport java.util.*;public class Main { static int n, m; static boolean test(int i, int j, char[][] v) { List<Character> x = new ArrayList<>(); for (int k = j; k < m; k++) { x.add(v[i][k]); } char[] temp = new char[x.size()]; for (int k = 0; k < x.size(); k++) { temp[k] = x.get(k); } if (isSorted(temp)) { return true; } return false; } static boolean isSorted(char[] arr) { for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { return false; } } return true; } static void solve(String[] strs) { n = strs.length; m = strs[0].length(); char[][] v = new char[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { v[i][j] = strs[i].charAt(j); } } int res = 0; for (int i = 0; i < n; i++) { int cnt = res; if (isSorted(v[i])) { cnt++; continue; } for (int j = cnt; j < m; j++) { if (test(i, j, v)) { break; } else { cnt++; } } res = cnt; } System.out.println(res); } public static void main(String[] args) { String[] v = { "hello", "neveropen" }; String[] x = { "xyz", "lmn", "pqr" }; solve(v); solve(x); }}// This code is contributed by pradeepkumarppk2003 |
Python3
import itertoolsn, m = 0,0def test(i, j, v): x = [] for k in range(j, m): x.append(v[i][k]) if(sorted(x) == x): return True return Falsedef solve(strs): global n, m n = len(strs) m = len(strs[0]) v = [[0 for j in range(m)] for i in range(n)] for i in range(n): for j in range(m): for k, val in enumerate(strs[i]): v[i][j+k] = val res = 0 for i in range(n): cnt = res if(sorted(v[i]) == v[i]): cnt += 1 continue for j in range(cnt, m): if(test(i, j, v)): break else: cnt += 1 res = cnt print(res)# Driver Codeif __name__ == "__main__": v = ["hello", "neveropen"] x = ["xyz", "lmn", "pqr"] solve(v) solve(x) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class MainClass { static int n, m; static bool Test(int i, int j, char[][] v) { List<char> x = new List<char>(); for (int k = j; k < m; k++) { x.Add(v[i][k]); } char[] temp = new char[x.Count]; for (int k = 0; k < x.Count; k++) { temp[k] = x[k]; } if (IsSorted(temp)) { return true; } return false; } static bool IsSorted(char[] arr) { for (int i = 0; i < arr.Length - 1; i++) { if (arr[i] > arr[i + 1]) { return false; } } return true; } static void Solve(string[] strs) { n = strs.Length; m = strs[0].Length; char[][] v = new char[n][]; for (int i = 0; i < n; i++) { v[i] = new char[m]; for (int j = 0; j < m; j++) { v[i][j] = strs[i][j]; } } int res = 0; for (int i = 0; i < n; i++) { int cnt = res; if (IsSorted(v[i])) { cnt++; continue; } for (int j = cnt; j < m; j++) { if (Test(i, j, v)) { break; } else { cnt++; } } res = cnt; } Console.WriteLine(res); } public static void Main() { string[] v = { "hello", "neveropen" }; string[] x = { "xyz", "lmn", "pqr" }; Solve(v); Solve(x); }} |
Javascript
function test(i, j, v) { let x = []; for (let k = j; k < m; k++) { x.push(v[i][k]); } if (x.every((val, index, arr) => !index || val >= arr[index - 1])) { return true; } return false;}function solve(strs) { n = strs.length; m = strs[0].length; let v = new Array(n).fill().map(() => new Array(m).fill()); for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { v[i][j] = strs[i].charAt(j); } } let res = 0; for (let i = 0; i < n; i++) { let cnt = res; if (v[i].every((val, index, arr) => !index || val >= arr[index - 1])) { cnt++; continue; } for (let j = cnt; j < m; j++) { if (test(i, j, v)) { break; } else { cnt++; } } res = cnt; } console.log(res);}let v = ["hello", "neveropen"];let x = ["xyz", "lmn", "pqr"];solve(v);solve(x); |
Output
1 0
Approach 2:
The idea of the problem is to find the columns to keep, instead of columns to delete. Finally we return the difference of the counted value with the length of the string. Now, let’s say we keep the first column C1. The next column C2 we must have all rows lexicographically sorted i.e. C1[i] <= C2[i] for all valid values of i and we say that we have deleted all columns between C1 and C2.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find minimum columns to be deletedint deleteColumns(vector<string>& A){ // Length of each string int l = A[0].length(); // Initialize dp array vector<int> dp(l, 1); for (int i = l - 2; i >= 0; i--) { for (int j = i + 1; j < l; j++) { bool flag = true; for (auto row : A) { if (row[i] > row[j]) { flag = false; break; } } if (flag) { dp[i] = max(dp[i], 1 + dp[j]); } } } // Return result return l - *max_element(dp.begin(), dp.end());}// Driver Codeint main(){ vector<string> arr = { "hello", "neveropen" }; vector<string> arr2 = { "xyz", "lmn", "pqr" }; // Function call to print required answer cout << deleteColumns(arr) << endl; cout << deleteColumns(arr2) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class Main { // Function to find minimum columns to be deleted static int deleteColumns(List<String> A) { // Length of each string int l = A.get(0).length(); // Initialize dp array int[] dp = new int[l]; Arrays.fill(dp, 1); for (int i = l - 2; i >= 0; i--) { for (int j = i + 1; j < l; j++) { boolean flag = true; for (String row : A) { if (row.charAt(i) > row.charAt(j)) { flag = false; break; } } if (flag) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } } // Return result return l - Arrays.stream(dp).max().getAsInt(); } // Driver Code public static void main(String[] args) { List<String> arr = Arrays.asList("hello", "neveropen"); List<String> arr2 = Arrays.asList("xyz", "lmn", "pqr"); // Function call to print required answer System.out.println(deleteColumns(arr)); System.out.println(deleteColumns(arr2)); }}// This code is contributed by Prince |
Python3
# Python3 implementation of the approach# Function to find minimum columns to be deleteddef deleteColumns(A): # Length of each string l = len(A[0]) # Initialize dp array dp = [1] * l for i in range(l - 2, -1, -1): for j in range(i + 1, l): if all(row[i] <= row[j] for row in A): dp[i] = max(dp[i], 1 + dp[j]) # Return result return l - max(dp)# Driver Codearr = ["hello", "neveropen"]arr2 = ["xyz", "lmn", "pqr"]# Function call to print required answerprint(deleteColumns(arr)+"<br>")print(deleteColumns(arr2)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;public class MainClass { // Function to find minimum columns to be deleted static int DeleteColumns(List<string> A) { // Length of each string int l = A[0].Length; // Initialize dp array int[] dp = new int[l]; Array.Fill(dp, 1); for (int i = l - 2; i >= 0; i--) { for (int j = i + 1; j < l; j++) { bool flag = true; foreach (string row in A) { if (row[i] > row[j]) { flag = false; break; } } if (flag) { dp[i] = Math.Max(dp[i], 1 + dp[j]); } } } // Return result return l - dp.Max(); } public static void Main() { List<string> arr = new List<string>() { "hello", "neveropen" }; List<string> arr2 = new List<string>() { "xyz", "lmn", "pqr" }; // Function call to print required answer Console.WriteLine(DeleteColumns(arr)); Console.WriteLine(DeleteColumns(arr2)); }}// This code is contributed by codebraxnzt |
Javascript
//JS code for the above approach// Function to find minimum columns to be deletedfunction deleteColumns(A) { // Length of each string let l = A[0].length; // Initialize dp array let dp = Array(l).fill(1); for (let i = l - 2; i >= 0; i--) { for (let j = i + 1; j < l; j++) { if (A.every(row => row[i] <= row[j])) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } } // Return result return l - Math.max(...dp);}// Driver Codelet arr = ["hello", "neveropen"];let arr2 = ["xyz", "lmn", "pqr"];// Function call to print required answerconsole.log(deleteColumns(arr));console.log(deleteColumns(arr2))// This code is contributed by lokeshpotta20. |
Output
1 0
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
