Find the longest palindrome in a string
https://leetcode.com/problems/longest-palindromic-substring/
Expand from center, check for even and odd palindromes
class Solution { public: string longestPalindrome(string s) { if (s.size() < 1) return ""; int start = 0; int l = s.size(); int maxLength = 1; for (int i = 0; i < l; i++) { // Odd int low = i - 1, high = i; while (low >= 0 && high < l && s[low] == s[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } low--; high++; } // Even low = i - 1, high = i + 1; while (low >= 0 && high < l && s[low] == s[high]) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } low--; high++; } } return s.
Minimum number of bracket reversals needed to make an expression balanced
https://practice.geeksforgeeks.org/problems/count-the-reversals/0
}{{}}{{{ Remove all valid pairs, remaining string is like }}}…{{{… ans = ceil(lBraces) + ceil(rBraces) in remaining string
int countRev(string s) { int n = s.size(); if (n % 2 != 0) return -1; stack<char> st; for (int i = 0; i < n; i++) { if (s[i] == '}' && !st.empty()) { if (st.top() == '{') st.pop(); else st.push(s[i]); } else st.push(s[i]); } int lCount = 0; while (!
Count of number of given string in 2D character array
https://www.geeksforgeeks.org/find-count-number-given-string-present-2d-character-array/
class Solution { bool searchUtil(int r, int c, string &word, vector<pair<int, int>> &dir, vector<vector<char>> &grid) { int R = grid.size(); int C = grid[0].size(); if (grid[r][c] != word[0]) { return false; } int len = word.length(); for (int i = 0; i < 8; i++) { int k = 1, rd = r + dir[i].first, cd = c + dir[i].second; while (k < len) { if (rd >= R || cd >= C || rd < 0 || cd < 0) { break; } if (grid[rd][cd] !
Longest common prefix
https://leetcode.com/problems/longest-common-prefix/
Divide and conquer, compare left and right subarrays.
class Solution { string lcp(vector<string> &strs, int l, int r) { if (l == r) return strs[l]; else { int mid = l + (r - l) / 2; string leftLCP = lcp(strs, l, mid); string rightLCP = lcp(strs, mid + 1, r); return commonPrefix(leftLCP, rightLCP); } } string commonPrefix(string left, string right) { int l = min(left.length(), right.length()); int ctr = 0; while (ctr < l && left[ctr] == right[ctr]) { ctr++; } return left.
Find the second most repeated word in string
https://practice.geeksforgeeks.org/problems/second-most-repeated-string-in-a-sequence/0
class Solution { public: string secFrequent(string arr[], int n) { map<string, int> mp; for (int i = 0; i < n; i++) { mp[arr[i]]++; } int maxFreq = -1, notMaxFreq = -1; string ans = ""; for (auto it : mp) { if (it.second > maxFreq) { notMaxFreq = maxFreq; maxFreq = it.second; } else if (it.second > notMaxFreq && it.second != maxFreq) { notMaxFreq = it.second; } } for (auto it : mp) { if (it.
Transform one string to another using minimum number of given operation
https://www.geeksforgeeks.org/transform-one-string-to-another-using-minimum-number-of-given-operation/
Check relative character frequencies & length of strings Start from end, increase res till character found in B Doing this because insertion is only allowed in front of A
#include <bits/stdc++.h> using namespace std; int minOps(string A, string B) { int n = A.length(), m = B.length(); if (n != m) return -1; map<char, pair<int, int>> mp; for (int i = 0; i < n; i++) { mp[A[i]].
Longest common subsequence
https://practice.geeksforgeeks.org/problems/longest-common-subsequence/0
Iterative
class Solution { int dp[1005][1005]; public: int lcs(int x, int y, string s1, string s2) { for (int i = 0; i <= x; i++) { for (int j = 0; j <= y; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[x][y]; } }; Recursive