Find last index of a character in a string

Find Minimum Indexed Character in String

Last Updated : 13 Aug, 2024

Try it on GfG Practice

Given a string str and another string patt. The task is to find the character in patt that is present at the minimum index in str. If no character of patt is present in str then print “$”.

Examples:

Input: str = “geeksforgeeks”, patt = “set”
Output: e
Both e and s of patt are present in str, but e is present at minimum index, which is 1.

Input: str = “adcffaet”, patt = “onkl”
Output: -1

Source: OLA Interview Experience

Table of Content

[Naive Approach] Using Two Nested Loops – O(m*n) Time and O(1) Space
[Expected Approach] Using Frequency Array – O(n) Time and O(1) Space
[Other Approach] Using Set or Hashing – O(n) Time and O(1) space

**[Naive Approach] Using Two Nested Loops – O(m*n) Time and O(1) Space**

The very simple approach to solve this problem is that we can use two nested loops: The outer loop goes through each character in str one by one. For each character in str, the inner loop checks if this character exists in patt. As soon as we find a match (i.e., a character in str that is also in patt), we return that character because it’s the first character from patt that appears in str. If no match is found after checking all characters, we return “$” to indicate that no characters from patt are present in str.

Below is the implementation of above approach:

C++

#include <bits/stdc++.h>
using namespace std;

// Function to print the minimum index character
// in a string.
string findMinIndexChar(const string &S, 
                        const string &patt) {
  
    // Iterate over each character in S
    for (int i = 0; i < S.length(); i++) {
      
        // For each character in S, iterate over
        // each character in patt
        for (int j = 0; j < patt.length(); j++) {
          
            // If a character in S matches a character 
            // in patt
            if (S[i] == patt[j]) {
              
                // Return the matched character
                return string(1, S[i]);
            }
        }
    }
    // If no match is found, return '$'
    return "$";
}

int main() {
    string S = "geeksforgeeks";
    string patt = "set";
    string result = findMinIndexChar(S, patt);
    cout << result;

    return 0;
}

C

#include <stdio.h>
#include <string.h>

// Function to print the minimum index character
// in a string.
char findMinIndexChar(const char *S, 
                      const char *patt) {

    // Iterate over each character in S
    for (int i = 0; S[i] != '\0'; i++) {
      
        // For each character in S, iterate over
        // each character in patt
        for (int j = 0; patt[j] != '\0'; j++) {
          
            // If a character in S matches a character 
            // in patt
            if (S[i] == patt[j]) {
              
                // Return the matched character
                return S[i];
            }
        }
    }
    // If no match is found, return '$'
    return '$';
}

int main() {
    char S[] = "geeksforgeeks";
    char patt[] = "set";
    char result = findMinIndexChar(S, patt);
    printf("%c\n", result);

    return 0;
}

Java

import java.util.*;

class GfG {

    // Function to print the minimum index character
    // in a string.
    static String findMinIndexChar(String S, 
                                   String patt) {
      
        // Iterate over each character in S
        for (int i = 0; i < S.length(); i++) {
          
            // For each character in S, iterate over
            // each character in patt
            for (int j = 0; j < patt.length(); j++) {
              
                // If a character in S matches a character 
                // in patt
                if (S.charAt(i) == patt.charAt(j)) {
                  
                    // Return the matched character
                    return String.valueOf(S.charAt(i));
                }
            }
        }
        // If no match is found, return "$"
        return "$";
    }

    public static void main(String[] args) {
        String S = "geeksforgeeks";
        String patt = "set";
        String result = findMinIndexChar(S, patt);
        System.out.println(result);
    }
}

Python

# Function to print the minimum index character
# in a string.
def find_min_index_char(S, patt):
    
    # Iterate over each character in S
    for i in range(len(S)):
        
        # For each character in S, iterate over
        # each character in patt
        for j in range(len(patt)):
            
            # If a character in S matches a character 
            # in patt
            if S[i] == patt[j]:
                
                # Return the matched character
                return S[i]
    
    # If no match is found, return '$'
    return '$'

S = "geeksforgeeks"
patt = "set"
result = find_min_index_char(S, patt)
print(result)

C#

using System;

class GfG {
    
    // Function to print the minimum index character
    // in a string.
    static string FindMinIndexChar(string S, 
                                   string patt) {
        
        // Iterate over each character in S
        for (int i = 0; i < S.Length; i++) {
            
            // For each character in S, iterate over
            // each character in patt
            for (int j = 0; j < patt.Length; j++) {
                
                // If a character in S matches a character 
                // in patt
                if (S[i] == patt[j]) {
                    
                    // Return the matched character
                    return S[i].ToString();
                }
            }
        }
        // If no match is found, return "$"
        return "$";
    }

    static void Main(string[] args) {
        string S = "geeksforgeeks";
        string patt = "set";
        string result = FindMinIndexChar(S, patt);
        Console.WriteLine(result);
    }
}

JavaScript

// Function to print the minimum index character
// in a string.
function findMinIndexChar(S, patt) {
  
    // Iterate over each character in S
    for (let i = 0; i < S.length; i++) {
      
        // For each character in S, iterate over
        // each character in patt
        for (let j = 0; j < patt.length; j++) {
          
            // If a character in S matches a character 
            // in patt
            if (S[i] === patt[j]) {
              
                // Return the matched character
                return S[i];
            }
        }
    }
    // If no match is found, return '$'
    return '$';
}

const S = "geeksforgeeks";
const patt = "set";
const result = findMinIndexChar(S, patt);
console.log(result);

Output

Time Complexity: O(m*n), where m and n are the lengths of the two strings.
Auxiliary Space: O(1)

[Expected Approach] Using Frequency Array – O(n) Time and O(1) Space

The idea is to create a frequency array of size 26, corresponding to each letter of the alphabet. This will count how many times each character appears in the patt. Then, iterates through str and check for each character against the frequency array. The first character found in str with a non-zero frequency indicates it is present in patt, and this character is returned. If no match is found, returns a special character ($).

C++

#include <bits/stdc++.h>
using namespace std;

// Function to print the minimum index character
// in a string.
string printMinIndexChar(string & str, string & patt) {
    // Creating a vector of size 26 to maintain
    // frequency of characters in patt.
    vector<int> hash(26, 0);
    
    // Iterating over each character in patt
    // and updating its frequency.
    for (auto i : patt) 
        hash[i - 'a']++;

    // Iterating over each character in str.
    for (auto i : str) {
      
        // If frequency of current character
        // in str is non-zero, we have found
        // the minimum index character.
        if (hash[i - 'a']) {
          return string(1, i);
        }
    }

    // If no minimum index character found
    return "$";
}

int main() {
    string str = "geeksforgeeks"; 
    string patt = "set";
    string result = printMinIndexChar(str, patt);
    cout << result << endl; 
    return 0;
}

C

#include <stdio.h>
#include <string.h>

// Function to print the minimum index character
// in a string.
char* printMinIndexChar(char *str, char *patt) {
    // Creating an array of size 26 to maintain
    // frequency of characters in patt.
    int hash[26] = {0};

    // Iterating over each character in patt
    // and updating its frequency.
    for (int i = 0; patt[i] != '\0'; i++) {
        hash[patt[i] - 'a']++;
    }

    // Iterating over each character in str.
    for (int i = 0; str[i] != '\0'; i++) {
        // If frequency of current character in str 
        // is non-zero, we have found the minimum
        // index character.
        if (hash[str[i] - 'a'] > 0) {
          
           // Creating a static array to store the answer.
            static char ans[2];
            ans[0] = str[i]; 
            ans[1] = '\0'; 
            return ans; 
        }
    }

    // If no minimum index character found
    return "$";
}

int main() {
    char str[] = "geeksforgeeks"; 
    char patt[] = "set"; 
    char *result = printMinIndexChar(str, patt); 
    printf("%s\n", result);
    return 0;
}

Java

class GfG {
    // Function to print the minimum index character in a
    // string.
    static char printMinIndexChar(String str,
                                         String patt)
    {
        // Creating an array to maintain frequency of
        // characters in patt.
        int[] hash = new int[26];

        // Iterating over each character in patt and
        // updating its frequency.
        for (char c : patt.toCharArray()) {
            hash[c - 'a']++;
        }

        // Iterating over each character in str.
        for (char c : str.toCharArray()) {
            // If frequency of current character in str is
            // non-zero, we have found the minimum index
            // character.
            if (hash[c - 'a'] > 0) {
              // Returning the minimum index
              // character.
                return c; 
            }
        }

        // If no minimum index character found
        return '$';
    }

    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        String patt = "set"; 
        char result = printMinIndexChar(
            str, patt); 
        System.out.println(result); 
    }
}

Python

def print_min_index_char(str, patt):
    # Creating a list to maintain frequency
    # of characters in patt.
    hash = [0] * 26

    # Iterating over each character in patt
    # and updating its frequency.
    for char in patt:
        hash[ord(char) - ord('a')] += 1

    # Iterating over each character in str.
    for char in str:

        # If frequency of current character
        # in str is non-zero, we have found
        # the minimum index character.
        if hash[ord(char) - ord('a')] > 0:
            # Returning the minimum index character.
            return char  

    # If no minimum index character found, return '$'.
    return '$'

if __name__ == "__main__":
    str = "geeksforgeeks" 
    patt = "set"  
    result = print_min_index_char(str, patt)  
    print(result)

C#

using System;

class GfG {
    // Function to print the minimum index character in a
    // string.
    static char PrintMinIndexChar(string str,
                                         string patt)
    {
        // Creating an array to maintain frequency of
        // characters in patt.
        int[] hash = new int[26];

        // Iterating over each character in patt and
        // updating its frequency.
        foreach(char c in patt) { hash[c - 'a']++; }

        // Iterating over each character in str.
        foreach(char c in str)
        {

            // If frequency of current character in str is
            // non-zero, we have found the minimum index
            // character.
            if (hash[c - 'a'] > 0) {

                // Returning the minimum index character.
                return c;
            }
        }

        // If no minimum index character found, return '$'.
        return '$';
    }

    static void Main()
    {
        string str = "geeksforgeeks"; 
        string patt = "set"; 
        char result = PrintMinIndexChar(
            str, patt);
        Console.WriteLine(result);
    }
}

JavaScript

function printMinIndexChar(str, patt)
{
    // Creating an array to maintain frequency of characters
    // in patt.
    let hash = new Array(26).fill(0);

    // Iterating over each character in patt and updating
    // its frequency.
    for (let char of patt) {
        hash[char.charCodeAt(0) - "a".charCodeAt(0)]++;
    }

    // Iterating over each character in str.
    for (let char of str) {
        // If frequency of current character in str is
        // non-zero, we have found the minimum index
        // character.
        if (hash[char.charCodeAt(0) - "a".charCodeAt(0)]
            > 0) {
            return char; // Returning the minimum index
                         // character.
        }
    }

    // If no minimum index character found, return '$'.
    return "$";
}

const str = "geeksforgeeks"; 
const patt = "set"; 
const result
    = printMinIndexChar(str, patt); 
console.log(result);

Output

Time Complexity: O(n), where n is the length of given string str
Auxiliary Space: O(1)

[Other Approach] Using Set or Hashing – O(n) Time and O(1) space

This idea is similar to the above discussed approach, instead of using frequency array of size 26, we can use any data structure like set or hash map. The idea it that first storing all characters from the pattern (patt) in a set or hash map, allowing for quick lookups. Then, iterates through the main string (str) to find the first character that exists in the set or hash map. If such character found then, this character is the one that appears at the minimum index in str and is also present in patt. If no such character is found, it returns “$” to indicate that none of the characters in patt are present in str

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

// Function to print the minimum index character
// in a string.
string printMinIndexChar(string & str, 
                         string & patt) {
    // Creating an unordered_map to store the characters 
    // of patt as keys and their presence as values.
    unordered_map<char, bool> hash;
    
    // Iterating over each character in patt and 
    // updating its presence.
    for (char ch : patt) 
        hash[ch] = true;

    // Iterating over each character in str.
    for (char ch : str) {
      
        // If current character in str is present
        // in the hash map, we have found the minimum
        // index character.
        if (hash[ch]) {
          
            // Returning the minimum index character
            // as a string.
            return string(1, ch);
        }
    }

    // If no minimum index character found
    return "$";
}

int main() {
    string str = "geeksforgeeks"; 
    string patt = "set";
    string result = printMinIndexChar(str, patt);
    cout << result << endl; 
    return 0;
}

Java

import java.util.*;

// Function to print the minimum index character 
// in a string.
class Main {
    static String printMinIndexChar(String str, 
                                    String patt) {
        // Creating a HashSet to store the presence of 
        // characters in patt.
        Set<Character> hash = new HashSet<>();
        
        // Iterating over each character in patt and 
        // updating its presence.
        for (char ch : patt.toCharArray()) 
            hash.add(ch);

        // Iterating over each character in str.
        for (char ch : str.toCharArray()) {
          
            // If current character in str is present
            // in the hash set, we have found the minimum
            // index character.
            if (hash.contains(ch)) {
              
                // Returning the minimum index character
                // as a string.
                return String.valueOf(ch);
            }
        }

        // If no minimum index character found
        return "$";
    }

    public static void main(String[] args) {
        String str = "geeksforgeeks"; 
        String patt = "set";
        String result = printMinIndexChar(str, patt);
        System.out.println(result); 
    }
}

Python

def minIndexChar(str, patt):
    # Dictionary to store the first index of each character in 'str'
    um = {}

    min_index = float('inf')

    m = len(str)
    n = len(patt)

    # Store the first index of each character of 'str'
    for i in range(m):
        if str[i] not in um:
            um[str[i]] = i

    # Traverse the string 'patt'
    for j in range(n):
        if patt[j] in um and um[patt[j]] < min_index:
            min_index = um[patt[j]]

    return min_index if min_index != float('inf') else -1

# Driver program to test above
if __name__ == "__main__":
    str1 = "geeksforgeeks"
    patt = "set"
    print(minIndexChar(str1, patt))  # Output: 1

C#

using System;
using System.Collections.Generic;

// Function to print the minimum index character 
// in a string.
class Program {
    static string printMinIndexChar(string str, 
                                    string patt) {
        // Creating a HashSet to store the presence of 
        // characters in patt.
        HashSet<char> hash = new HashSet<char>();
        
        // Iterating over each character in patt and 
        // updating its presence.
        foreach (char ch in patt)
            hash.Add(ch);

        // Iterating over each character in str.
        foreach (char ch in str) {
          
            // If current character in str is present
            // in the hash set, we have found the minimum
            // index character.
            if (hash.Contains(ch)) {
              
                // Returning the minimum index character
                // as a string.
                return ch.ToString();
            }
        }

        // If no minimum index character found
        return "$";
    }

    static void Main(string[] args) {
        string str = "geeksforgeeks"; 
        string patt = "set";
        string result = printMinIndexChar(str, patt);
        Console.WriteLine(result); 
    }
}

JavaScript

// Function to print the minimum index character 
// in a string.
function printMinIndexChar(str, patt) {
    // Creating a Set to store the presence of 
    // characters in patt.
    let hash = new Set();
    
    // Iterating over each character in patt and 
    // updating its presence.
    for (let ch of patt) 
        hash.add(ch);

    // Iterating over each character in str.
    for (let ch of str) {
      
        // If current character in str is present
        // in the hash set, we have found the minimum
        // index character.
        if (hash.has(ch)) {
          
            // Returning the minimum index character
            // as a string.
            return ch;
        }
    }

    // If no minimum index character found
    return "$";
}

let str = "geeksforgeeks"; 
let patt = "set";
let result = printMinIndexChar(str, patt);
console.log(result);

Output

Time Complexity: O(m + n), where m and n are the lengths of the two strings.
Auxiliary Space: O(1)

Find last index of a character in a string

GeeksforGeeks

News

Improve

Article Tags :

Practice Tags :

Similar Reads

Find Minimum Indexed Character in String

Given a string str and another string patt. The task is to find the character in patt that is present at the minimum index in str. If no character of patt is present in str then print "$". Examples: Input: str = "geeksforgeeks", patt = "set" Output: e Both e and s of patt are present in str, but e i

Find last index of a character in a string

Given a string str and a character x, find last index of x in str. Examples : Input : str = "geeks", x = 'e' Output : 2 Last index of 'e' in "geeks" is: 2 Input : str = "Hello world!", x = 'o' Output : 7 Last index of 'o' is: 7 Recommended PracticeLast index of a character in the stringTry It! Metho

Find one extra character in a string

Given two strings which are of lengths n and n+1. The second string contains all the characters of the first string, but there is one extra character. Your task is to find the extra character in the second string. Examples: Input : string strA = "abcd"; string strB = "cbdae"; Output : e string B con

Find maximum occurring character in a string

Given string str. The task is to find the maximum occurring character in the string str. Examples: Input: geeksforgeeksOutput: eExplanation: 'e' occurs 4 times in the string Input: testOutput: tExplanation: 't' occurs 2 times in the string Recommended PracticeEncrypt the string - 1Try It!Return the

Remove odd indexed characters from a given string

Given string str of size N, the task is to remove the characters present at odd indices (0-based indexing) of a given string. Examples : Input: str = â€œabcdefâ€Output: aceExplanation:The characters 'b', 'd' and 'f' are present at odd indices, i.e. 1, 3 and 5 respectively. Therefore, they are removed f

Find first non-repeating character of given string

Given a string s of lowercase English letters, the task is to find the first non-repeating character. If there is no such character, return '$'. Examples: Input: s = "geeksforgeeks"Output: 'f'Explanation: 'f' is the first character in the string which does not repeat. Input: s = "racecar"Output: 'e'

Find repeated character present first in a string

Given a string, find the repeated character present first in the string.(Not the first repeated character, found here.) Examples: Input : geeksforgeeks Output : g (mind that it will be g, not e.) Asked in: Goldman Sachs internship Simple Solution using O(N^2) complexity: The solution is to loop thro

Queries for characters in a repeated string

Given a string, X. Form a string S by repeating string X multiple times i.e appending string X multiple times with itself. There are Q queries of forms i and j. The task is to print "Yes" if the element at index i is the same as the element at index j in S else print "No" for each query. Examples :

Accessing characters by index in a String

Given two strings str1 and an index, the task is to access the character at this index. Examples: Input: str = "hello", index = 1Output: e Input: str = "GfG", index = 2Output: G Accessing characters by index in a string:Individual characters in a string can be accessed by specifying the string name

Find characters which when increased by K are present in String

Given a string s of lowercase English alphabets and integer K. the task is to check if each character after increasing their ASCII by K is present in the string or not. Return only unique characters and the first index where they are present. Examples: Input: s = "dszepvaxuo", k = 3Output: {{1, 's'}

翻译：