Recent advances in Explainable Artificial Intelligence (XAI) have enabled the development of solutions using diverse Deep Learning architectures, including Graph Neural Networks (GNNs). Most GNN explainability methods identify explanation subgraphs by ranking elements based on importance scores or masks. However, these approaches often rely on hyperparameters to determine subgraph size, which is impractical for real-world datasets lacking ground-truth explanations. Moreover, ranking-based methods only indirectly reflect each element's contribution to the decision-making process, potentially yielding inconsistent results. To address these limitations, we introduce DotGreedX, a two-step, hyperparameter-free explainer that combines a scoring-based technique with a greedy search algorithm to identify optimal-size explanation subgraphs for each input graph. Our method leverages robust evaluation metrics to ensure high-quality explanations. Experiments on five benchmark molecular datasets demonstrate state-of-the-art performance, and we show that our greedy search algorithm can also enhance the results of other explainability methods.