Scribd
Upload
7 views

LeetcodeDay 23

Uploaded by

dhruuvnaik5702
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views

LeetcodeDay 23

Uploaded by

dhruuvnaik5702
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

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)

You might also like