GDSC-DBIT DSA Leetcode 45 (Day-23)
Question 1: 2828. Check if a String Is an Acronym of Words
Tags: Array String
PseudoCode:-
// Function to check if the concatenated first characters of words form the given acronym
function isAcronym(words: List<String>, s: String) -> boolean:
// Initialize a StringBuilder to store the first characters of each word
StringBuilder sb = new StringBuilder()
// Iterate through each word in the list
for st in words:
// Append the first character of each word to the StringBuilder
sb.append(st.charAt(0))
// Check if the concatenated first characters match the given acronym
return sb.toString().equals(s)
Time Complexity: O(n)
Space Complexity: O(n)
Question 2: 2942. Find Words Containing Character
Tags: Array String
PseudoCode:-
// Function to find the indices of words containing a specific character
function findWordsContaining(words: Array of String, x: char) -> List of Integer:
// Initialize an empty list to store the indices of words containing the character
List of Integer list = []
// Initialize an index counter
Integer i = 0
// Iterate through each string in the array
for string in words
if string contains x :
list.add(i)
// Increment the index counter
i++
// Return the list of indices
return list
Time Complexity: O(n)
Space Complexity: O(n)
Question 3: 763. Partition Labels
Tags: Hash Table Two Pointers String Greedy
PseudoCode:-
Approach 1: Using Hash Table
// Function to find the lengths of partitions in a string where each letter appears in at most one part
function findPartitionLengths(s: String) -> List of Integer:
// Initialize a HashMap to store the last occurrence index of each character
Map<Character, Integer> map = new HashMap<>();
// Convert the input string to a character array
char[] arr = s.toCharArray();
// Initialize a list to store the lengths of the partitions
List<Integer> list = new ArrayList<>();
// Populate the HashMap with the last occurrence index of each character
for i from 0 to length of s - 1:
map.put(s.charAt(i), i);
// Initialize variables to track the maximum index and the start of the current partition
int max = map.get(arr[0]);
int prev = 0;
// Iterate through the string to find partition lengths
for i from 0 to length of s - 1:
// Update the maximum index encountered so far
max = max(max, map.get(arr[i]));
// If the maximum index equals the current index, it indicates the end of a partition
if max equals i:
// Add the length of the current partition to the list
list.add(max - prev + 1);
// Update the start of the next partition
prev = max + 1;
// Return the list of partition lengths
return list
Time Complexity: O(n )
Space Complexity: O(n)
Approach 2: Using Two Pointer
// Function to partition a string into as many parts as possible, where each letter appears in at
most one part
function partitionLabels(s: String) -> List of Integer:
// Initialize an array to store the last occurrence index of each character in the string
int[] last = new int[26]
// Iterate through the string from right to left to record the last occurrence index of each
character
for i from s.length() - 1 to 0:
char ch = s.charAt(i)
if last[ch - 'a'] == 0:
last[ch - 'a'] = i
// Initialize a list to store the lengths of the partitions
List of Integer list = new LinkedList<Integer>()
// Initialize pointers i and j
int i = -1
int j = 0
// Initialize the character and its last occurrence index for the first partition
char ch = s.charAt(j)
int idx = last[ch - 'a']
// Iterate through the string
while true:
// If j reaches the last occurrence index of the current character
if j equals idx:
// Add the length of the current partition to the list
list.add(j - i)
// Update i to the current position
i=j
// Increment j
j++
// Break out of the loop if j reaches the end of the string
if j equals s.length():
break
// Update the character and its last occurrence index for the next partition
ch = s.charAt(j)
idx = max(idx, last[ch - 'a'])
// Return the list of partition lengths
return list
Time Complexity: O(n )
Space Complexity: O(n)
