Skip to main content

Minimum Indexed Character

Problem​

Given a string str and another string patt, find the minimum index of the character in str that is also present in patt.

Examples​

Example 1:

Input:
str = "geeksforgeeks"
patt = "set"

Output:
1

Explanation:
'e' is the character which is present in the given string "geeksforgeeks" and is also present in "set". The minimum index of 'e' is 1.

Example 2:

Input:
str = "adcffaet"
patt = "onkl"

Output:
-1

Explanation:
There are no characters that are common in "patt" and "str".

Your Task​

You only need to complete the function minIndexChar() that returns the index of the answer in str or returns -1 if no character of patt is present in str.

Expected Time Complexity: O(N)O(N) Expected Auxiliary Space: O(Numberofdistinctcharacters)O(Number of distinct characters)

Constraints​

  • 1≤∣str∣,∣patt∣≤1051 ≤ |str|,|patt| ≤ 10^5
  • ′a′≤str[i],patt[i]≤′z′'a' ≤ str[i], patt[i] ≤ 'z'

Solution​

Approach​

To solve this problem, we can follow these steps:

  1. Iterate through the characters in the patt string.
  2. For each character in patt, find its index in the str string using the find method.
  3. Store the indices in a vector.
  4. Iterate through the vector to find the minimum index that is not -1 (indicating the character is found in str).
  5. If no valid index is found, return -1; otherwise, return the minimum index.

Implementation​

class Solution
{
public:
int minIndexChar(string str, string patt)
{
int res = INT_MAX;
vector<int> v1;
for (int i = 0; i < patt.length(); i++)
{
int p = str.find(patt[i]);
v1.push_back(p);
}
int min = INT_MAX;
for (int i = 0; i < v1.size(); i++)
{
if (min > v1[i] && v1[i] != -1)
min = v1[i];
}
if (min == INT_MAX)
return -1;
return min;
}
};

Complexity Analysis​

  • Time Complexity: O(N)O(N), where N is the length of the string str. We iterate through each character in patt and use the find or indexOf method, which runs in O(N)O(N) time.
  • Space Complexity: O(1)O(1), as we only use a constant amount of extra space for variables.

References​