Untitled

class Solution {
public:
    int prefixConnected(vector<string>& words, int k) {
        
        map<string,int> mp;  
        // mp stores:
        // key   -> prefix of length k
        // value -> number of words having that prefix
        
        // Traverse each word
        for(auto it : words){
            
            string sk;              // To build prefix of length k
            int sz = it.size();
            
            // Ignore words shorter than k
            if(sz < k) continue;
            
            // Extract first k characters
            for(int j = 0; j < k; j++){
                sk.push_back(it[j]);
            }
            
            // Increase frequency of this prefix
            mp[sk]++;
        }

        int ans = 0;   // Counts connected groups
        
        // Count prefixes that appear at least twice
        // Since a valid connected group must have ≥ 2 words
        for(auto it : mp){
            if(it.second >= 2) ans++;
        }

        return ans;

        /*
        Time Complexity (TC):
        Let n = words.size()

        For each word:
        - Extracting prefix takes O(k)
        - Map insertion/update takes O(log n) comparisons,
        and each comparison costs O(k) (string comparison)

        So per word cost = O(k log n)

        Total TC = O(n * k * log n)


        Space Complexity (SC):
        In worst case, we store up to n different prefixes,
        each of length k.
        So SC = O(n * k)
        */
    }
};