Q1)
You are given a string consisting of lowercase English letters and # characters.
A # acts as a blocker, meaning a safe path cannot cross it.
Find the longest safe path, where a safe path is defined as the longest continuous substring containing only lowercase letters and no #.
If multiple substrings have the same maximum length, return any one of them.
Input:
ab#cdef##gh
Output:
cdef
Solution: Traverse the string
TC: O(N) , SC: O(1)
public class LongestSafePath {
public static String longestSafePath(String s) {
int start = 0;
int maxStart = 0;
int count = 0;
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '#') {
if (count > maxLen) {
maxLen = count;
maxStart = start;
}
count = 0;
start = i + 1;
} else {
count++;
}
}
// Final check in case string does not end with '#'
if (count > maxLen) {
maxLen = count;
maxStart = start;
}
return s.substring(maxStart, maxStart + maxLen);
}
public static void main(String[] args) {
String s = "ab#cdef##gh";
System.out.println(longestSafePath(s));
}}
Q2)
Follow up: What if we allow one hash to be considered safe.
input: ab##cde#fghij so segmenet [2,0,3,5]
Solution: Sliding window by keeping 1 # in substring
TC: O(N) , SC: O(1)
public class LongestSafePathSlidingWindowString {
public static String longestSafePath(String s) {
int left = 0;
int hashCount = 0;
int maxLen = 0;
int startIndex = 0;
for (int right = 0; right < s.length(); right++) {
if (s.charAt(right) == '#') {
hashCount++;
}
// Window invalid
while (hashCount > 1) {
if (s.charAt(left) == '#') {
hashCount--;
}
left++;
}
int currentLen = right - left + 1;
if (currentLen > maxLen) {
maxLen = currentLen;
startIndex = left;
}
}
return s.substring(startIndex, startIndex + maxLen);
}
public static void main(String[] args) {
String s = "ab#cdef##ghij";
System.out.println(longestSafePath(s));
}}
Q3)Don't remember the exact question but it was on string matching and two pointers.
Solved all the 3 questions and moved to 2nd round with final compensation after 3 Interviews- 36lpa for 1st year.
